www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Eliding of slice range checking

reply Per =?UTF-8?B?Tm9yZGzDtnc=?= <per.nordlow gmail.com> writes:
Does DMD/LDC avoid range-checking in slice-expressions such as 
the one in my array-overload of `startsWith` defined as

bool startsWith(T)(scope const(T)[] haystack,
                    scope const(T)[] needle)
{
     if (haystack.length >= needle.length)
     {
         return haystack[0 .. needle.length] == needle; // is 
slice range checking avoid here?
     }
     return false;
}

///
 safe pure nothrow  nogc unittest
{
     auto x = "beta version";
     assert(x.startsWith("beta"));
}

when building in release mode?

I remember a DMD pull from Ian Buclaw that enabled some eliding 
but I don't remember if it includes the case above.

How can I investigate the codegen myself here?
Oct 23 2019
next sibling parent reply kinke <kinke gmx.net> writes:
On Wednesday, 23 October 2019 at 11:20:59 UTC, Per Nordlöw wrote:
 How can I investigate the codegen myself here?
Simply check the IR or asm, e.g., on run.dlang.io. If there's a call to `_d_arraybounds` in the function of interest, bounds checks are enabled. For your example, the template is inferred to be safe, and `-release` only elides bounds checks in system functions (corresponding to `-boundscheck=safeonly`). Use `-boundscheck=off` to elide it in all functions.
Oct 23 2019
next sibling parent reply Per =?UTF-8?B?Tm9yZGzDtnc=?= <per.nordlow gmail.com> writes:
On Wednesday, 23 October 2019 at 11:33:56 UTC, kinke wrote:
 For your example, the template is inferred to be  safe, and 
 `-release` only elides bounds checks in  system functions 
 (corresponding to `-boundscheck=safeonly`). Use 
 `-boundscheck=off` to elide it in all functions.
Thanks. But I'm talking about the compiler being able to figure out that the expression haystack[0 .. needle.length] _never_ (regardless of compiler flags) needs any range checking because it is _only_ run when haystack.length >= needle.length . Do you follow?
Oct 23 2019
parent reply Stefan Koch <uplink.coder googlemail.com> writes:
On Wednesday, 23 October 2019 at 12:01:47 UTC, Per Nordlöw wrote:
 On Wednesday, 23 October 2019 at 11:33:56 UTC, kinke wrote:
 For your example, the template is inferred to be  safe, and 
 `-release` only elides bounds checks in  system functions 
 (corresponding to `-boundscheck=safeonly`). Use 
 `-boundscheck=off` to elide it in all functions.
Thanks. But I'm talking about the compiler being able to figure out that the expression haystack[0 .. needle.length] _never_ (regardless of compiler flags) needs any range checking because it is _only_ run when haystack.length >= needle.length . Do you follow?
Actually what you want is that the compiler uses a loop-invariant to only to bounds-checking once on the first loop entry? That's quite tricky to do for all cases. What you can do manually is to index the .ptr property which will decay the array to a pointer, and on a pointer you cannot and therefore will not do boundschecking just replace x = a[i] with x = a.ptr[i];
Oct 25 2019
parent reply =?UTF-8?Q?Ali_=c3=87ehreli?= <acehreli yahoo.com> writes:
On 10/25/2019 05:37 AM, Stefan Koch wrote:

 just replace x = a[i] with x = a.ptr[i];
That's a neat trick! Ali
Oct 25 2019
parent reply Per =?UTF-8?B?Tm9yZGzDtnc=?= <per.nordlow gmail.com> writes:
On Friday, 25 October 2019 at 15:22:12 UTC, Ali Çehreli wrote:
 On 10/25/2019 05:37 AM, Stefan Koch wrote:

 just replace x = a[i] with x = a.ptr[i];
That's a neat trick! Ali
But it requires the function to be qualified as trusted which might hide a system == operator. How common is it for a == operator to be unsafe?
Oct 25 2019
parent Per =?UTF-8?B?Tm9yZGzDtnc=?= <per.nordlow gmail.com> writes:
On Friday, 25 October 2019 at 21:33:26 UTC, Per Nordlöw wrote:
 But it requires the function to be qualified as  trusted which 
 might hide a  system == operator. How common is it for a == 
 operator to be unsafe?
Ping.
Oct 29 2019
prev sibling parent reply Per =?UTF-8?B?Tm9yZGzDtnc=?= <per.nordlow gmail.com> writes:
On Wednesday, 23 October 2019 at 11:33:56 UTC, kinke wrote:
 Simply check the IR or asm, e.g., on run.dlang.io. If there's a 
 call to `_d_arraybounds` in the function of interest, bounds 
 checks are enabled.
The ASM- and IR-output from the following code is pretty messy for ldc with flags `-release -O` Is it possible to remove cluttering? https://run.dlang.io/is/mAXOm6
Oct 23 2019
next sibling parent reply kinke <kinke gmx.net> writes:
On Wednesday, 23 October 2019 at 13:08:34 UTC, Per Nordlöw wrote:
 The ASM- and IR-output from the following code is pretty messy 
 for
You call this messy?! cmpq %rdi, %rdx jae .LBB0_2 xorl %eax, %eax retq .LBB0_2: movq %rdi, %rax testq %rdi, %rdi je .LBB0_3 pushq %rax .cfi_def_cfa_offset 16 movq %rcx, %rdi movq %rax, %rdx callq memcmp PLT testl %eax, %eax sete %al addq $8, %rsp .cfi_def_cfa_offset 8 retq .LBB0_3: movb $1, %al retq Anyway, clearly no bounds checks, LLVM's optimizer works as it should.
Oct 23 2019
parent Per =?UTF-8?B?Tm9yZGzDtnc=?= <per.nordlow gmail.com> writes:
On Wednesday, 23 October 2019 at 13:51:19 UTC, kinke wrote:
 You call this messy?!

 cmpq	%rdi, %rdx
 	jae	.LBB0_2
 	xorl	%eax, %eax
 	retq
 .LBB0_2:
 	movq	%rdi, %rax
 	testq	%rdi, %rdi
 	je	.LBB0_3
 	pushq	%rax
 	.cfi_def_cfa_offset 16
 	movq	%rcx, %rdi
 	movq	%rax, %rdx
 	callq	memcmp PLT
 	testl	%eax, %eax
 	sete	%al
 	addq	$8, %rsp
 	.cfi_def_cfa_offset 8
 	retq
 .LBB0_3:
 	movb	$1, %al
 	retq
No, this is fine. Thanks.
Oct 29 2019
prev sibling parent reply kinke <kinke gmx.net> writes:
On Wednesday, 23 October 2019 at 13:08:34 UTC, Per Nordlöw wrote:
 Is it possible to remove cluttering?
godbolt.org supports D as well and is way more powerful than run.dlang.io, besides offering way more LDC versions to choose from. It can also be used to remove the 'cluttering': https://d.godbolt.org/z/ejEmrK
Oct 23 2019
parent Per =?UTF-8?B?Tm9yZGzDtnc=?= <per.nordlow gmail.com> writes:
On Wednesday, 23 October 2019 at 14:52:42 UTC, kinke wrote:
 godbolt.org supports D as well and is way more powerful than 
 run.dlang.io, besides offering way more LDC versions to choose 
 from. It can also be used to remove the 'cluttering': 
 https://d.godbolt.org/z/ejEmrK
Very useful. Especially the mouse-over features for if and return statements. Are there any more D-code constructs that gets in assembly?
Oct 24 2019
prev sibling next sibling parent reply welkam <wwwelkam gmail.com> writes:
On Wednesday, 23 October 2019 at 11:20:59 UTC, Per Nordlöw wrote:
 Does DMD/LDC avoid range-checking in slice-expressions such as 
 the one in my array-overload of `startsWith` defined as

 bool startsWith(T)(scope const(T)[] haystack,
                    scope const(T)[] needle)
 {
     if (haystack.length >= needle.length)
     {
         return haystack[0 .. needle.length] == needle; // is 
 slice range checking avoid here?
     }
     return false;
 }

 ///
  safe pure nothrow  nogc unittest
 {
     auto x = "beta version";
     assert(x.startsWith("beta"));
 }

 when building in release mode?

 I remember a DMD pull from Ian Buclaw that enabled some eliding 
 but I don't remember if it includes the case above.

 How can I investigate the codegen myself here?
I remember in some video Chandler Carruth said that value range propagation across function boundary was implemented in llvm but later removed because it produced no performance improvement for C and C++ code. I wonder how it fare when used on D code.
Oct 24 2019
parent reply Per =?UTF-8?B?Tm9yZGzDtnc=?= <per.nordlow gmail.com> writes:
On Thursday, 24 October 2019 at 18:37:05 UTC, welkam wrote:
 I remember in some video Chandler Carruth said that value range 
 propagation across function boundary was implemented in llvm 
 but later removed because it produced no performance 
 improvement for C and C++ code. I wonder how it fare when used 
 on D code.
Interesting. What uses of VRP do you see in D?
Oct 24 2019
parent welkam <wwwelkam gmail.com> writes:
On Thursday, 24 October 2019 at 21:02:03 UTC, Per Nordlöw wrote:
 On Thursday, 24 October 2019 at 18:37:05 UTC, welkam wrote:
 I remember in some video Chandler Carruth said that value 
 range propagation across function boundary was implemented in 
 llvm but later removed because it produced no performance 
 improvement for C and C++ code. I wonder how it fare when used 
 on D code.
Interesting. What uses of VRP do you see in D?
Now that you asked I realized that it wont be that much useful because in D all arrays go together with their size so cross function VRP would do little.
Oct 25 2019
prev sibling next sibling parent Kagamin <spam here.lot> writes:
On Wednesday, 23 October 2019 at 11:20:59 UTC, Per Nordlöw wrote:
 Does DMD/LDC avoid range-checking in slice-expressions such as 
 the one in my array-overload of `startsWith` defined as

 bool startsWith(T)(scope const(T)[] haystack,
                    scope const(T)[] needle)
 {
     if (haystack.length >= needle.length)
     {
         return haystack[0 .. needle.length] == needle; // is 
 slice range checking avoid here?
     }
     return false;
 }
LDC is good at optimizing simple patterns, the only pitfall I know is https://forum.dlang.org/post/eoftnwkannqmubhjotat forum.dlang.org
Oct 29 2019
prev sibling parent Kagamin <spam here.lot> writes:
On Wednesday, 23 October 2019 at 11:20:59 UTC, Per Nordlöw wrote:
 Does DMD/LDC avoid range-checking in slice-expressions such as 
 the one in my array-overload of `startsWith` defined as

 bool startsWith(T)(scope const(T)[] haystack,
                    scope const(T)[] needle)
 {
     if (haystack.length >= needle.length)
     {
         return haystack[0 .. needle.length] == needle; // is 
 slice range checking avoid here?
     }
     return false;
 }
LDC is good at optimizing simple patterns, the only pitfall I know is https://forum.dlang.org/post/eoftnwkannqmubhjotat forum.dlang.org
Oct 31 2019