www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Dynamic array comparison optimization: check for equal pointers?

reply Johan <j j.nl> writes:
Hi all,
   I thought that we optimized dynamic array comparison with a 
check to see if the pointers are equal, but I don't see it in our 
array comparison implementation in druntime. Quick checking of 
glibc memcmp also showed that there is no short circuit for when 
the pointers of the slices are equal.

I was expecting something like:
```
   if ( sizes are not equal )
      return false;
   if ( pointers are equal  )
      return true;
   return memcmp;
```

I am surprised that memcmp itself does not implement the pointers 
are equal check. Is there a big impact of adding the shortcircuit 
check to prevent scanning memory?

cheers,
   Johan
Jun 02
next sibling parent Stefan Koch <uplink.coder googlemail.com> writes:
On Tuesday, 2 June 2020 at 19:38:04 UTC, Johan wrote:
 Hi all,
   I thought that we optimized dynamic array comparison with a 
 check to see if the pointers are equal, but I don't see it in 
 our array comparison implementation in druntime. Quick checking 
 of glibc memcmp also showed that there is no short circuit for 
 when the pointers of the slices are equal.

 I was expecting something like:
 ```
   if ( sizes are not equal )
      return false;
   if ( pointers are equal  )
      return true;
   return memcmp;
 ```

 I am surprised that memcmp itself does not implement the 
 pointers are equal check. Is there a big impact of adding the 
 shortcircuit check to prevent scanning memory?

 cheers,
   Johan
I would have expected this optimization to be present as well ... It seems like a no-brainer.
Jun 02
prev sibling next sibling parent reply Stanislav Blinov <stanislav.blinov gmail.com> writes:
On Tuesday, 2 June 2020 at 19:38:04 UTC, Johan wrote:

 I was expecting something like:
 ```
   if ( sizes are not equal )
      return false;
   if ( pointers are equal  )
      return true;
   return memcmp;
 ```
That's, worst case, two branches and a scan, and best case one branch which may or may not be slower than the actual scan.
 I am surprised that memcmp itself does not implement the 
 pointers are equal check. Is there a big impact of adding the 
 shortcircuit check to prevent scanning memory?
There can't be a definitive answer for this, it's dependent on architecture as well as size of data. As far as array comparison goes, if a compiler (talking about ldc/gdc here) can infer pointer/length information, it'll be free to throw away the scan. In all other cases, I'd rather see the comparison function, well, do the comparison, and leave branches up to the user. It's much better than to inflict the branches on everyone unconditionally (pun intended): if your data shows that you can benefit from the short-circuit, you can always do just that. Short of rethinking the design, of course ;) I mean, I can't imagine a scenario where a program would have to routinely compare identical memory ranges. Doesn't mean there aren't such scenarios though.
Jun 02
parent reply Johan <j j.nl> writes:
On Tuesday, 2 June 2020 at 20:54:39 UTC, Stanislav Blinov wrote:
 On Tuesday, 2 June 2020 at 19:38:04 UTC, Johan wrote:

 I was expecting something like:
 ```
   if ( sizes are not equal )
      return false;
   if ( pointers are equal  )
      return true;
   return memcmp;
 ```
That's, worst case, two branches and a scan, and best case one branch which may or may not be slower than the actual scan.
The "actual scan" is a function call, which will be super slow (note that in druntime's implementation it cannot be optimized to a tail call) compared to the comparison and early return.
 I am surprised that memcmp itself does not implement the 
 pointers are equal check. Is there a big impact of adding the 
 shortcircuit check to prevent scanning memory?
There can't be a definitive answer for this, it's dependent on architecture as well as size of data. As far as array comparison goes, if a compiler (talking about ldc/gdc here) can infer pointer/length information, it'll be free to throw away the scan. In all other cases, I'd rather see the comparison function, well, do the comparison, and leave branches up to the user. It's much better than to inflict the branches on everyone unconditionally (pun intended): if your data shows that you can benefit from the short-circuit, you can always do just that. Short of rethinking the design, of course ;) I mean, I can't imagine a scenario where a program would have to routinely compare identical memory ranges. Doesn't mean there aren't such scenarios though.
You are assuming that an if-statement costs significant time, but that doesn't have to be the case. The pointer values already must be read from memory (otherwise you cannot do the memory scan), and with speculative execution the comparison+branch only costs very little (codegen could be coaxed to make if(false) be the default execution path) and potentially saves many many memory reads. Could someone take the effort and check the performance difference (for example the compiler itself) with this change? Thanks! Johan
Jun 02
parent reply Stanislav Blinov <stanislav.blinov gmail.com> writes:
On Tuesday, 2 June 2020 at 22:01:20 UTC, Johan wrote:
 On Tuesday, 2 June 2020 at 20:54:39 UTC, Stanislav Blinov wrote:
 That's, worst case, two branches and a scan, and best case one 
 branch which may or may not be slower than the actual scan.
The "actual scan" is a function call, which will be super slow (note that in druntime's implementation it cannot be optimized to a tail call) compared to the comparison and early return.
LDC (and I'm assuming GDC as well) is well aware of memcmp, it should not be a function call. At the very least in -Ox builds.
 You are assuming that an if-statement costs significant time, 
 but that doesn't have to be the case. The pointer values 
 already must be read from memory (otherwise you cannot do the 
 memory scan), and with speculative execution the 
 comparison+branch only costs very little (codegen could be 
 coaxed to make if(false) be the default execution path) and 
 potentially saves many many memory reads.
I'm not assuming anything. The branch(es) may, or may not, be more costly than just comparing some words. Depending on architecture and the amount of data to compare. That's literally what I wrote :) May, or may not - implementation has no business assuming either way. That's why such a check absolutely should *not* be there. It should be where it belongs - in user code, backed up by profiling as necessary. Including it there may be beneficial for you specifically, but detrimental for everyone else.
Jun 02
parent reply Steven Schveighoffer <schveiguy gmail.com> writes:
On 6/2/20 6:20 PM, Stanislav Blinov wrote:
 On Tuesday, 2 June 2020 at 22:01:20 UTC, Johan wrote:
 On Tuesday, 2 June 2020 at 20:54:39 UTC, Stanislav Blinov wrote:
 That's, worst case, two branches and a scan, and best case one branch 
 which may or may not be slower than the actual scan.
The "actual scan" is a function call, which will be super slow (note that in druntime's implementation it cannot be optimized to a tail call) compared to the comparison and early return.
LDC (and I'm assuming GDC as well) is well aware of memcmp, it should not be a function call. At the very least in -Ox builds.
Let's assume LDC knows how to optimize this. How do you think it would do so? I'd imagine very similarly to how Johan wrote it. What makes you think LDC can't optimize out the check if there's a better way? Then the check is there in case the optimizer you are dealing with is going to call an opaque memcmp in all cases. -Steve
Jun 02
parent reply Stanislav Blinov <stanislav.blinov gmail.com> writes:
On Tuesday, 2 June 2020 at 22:44:24 UTC, Steven Schveighoffer 
wrote:

 Let's assume LDC knows how to optimize this. How do you think 
 it would do so? I'd imagine very similarly to how Johan wrote 
 it.

 What makes you think LDC can't optimize out the check if 
 there's a better way? Then the check is there in case the 
 optimizer you are dealing with is going to call an opaque 
 memcmp in all cases.
That actually is irrelevant. Whether it gets inlined, whether even it's loop is unrolled by the compiler - that is all beside the point. If you hardcode the check in the library, that check is there for everyone using that library. On all hardware and for all data sizes. Irrespective of whether it can, on a given platform with a given array size, be actually faster to just do the call/loop/etc. than to do a check first. Irrespective of what a given compiler is capable of. There cannot be a universal optimization here. Users can always write a compare_arrays_ptrcheck if so required, but they cannot "unwrite" druntime. Same goes for actual memcmp. So let them do the minimal work required, and let users make higher-level decisions at higher level. If a program is attempting to "compare" identical memory ranges so often as to warrant a test - it's up to that program to deal with it, not the whole community.
Jun 02
parent reply Steven Schveighoffer <schveiguy gmail.com> writes:
On 6/2/20 7:35 PM, Stanislav Blinov wrote:
 On Tuesday, 2 June 2020 at 22:44:24 UTC, Steven Schveighoffer wrote:
 
 Let's assume LDC knows how to optimize this. How do you think it would 
 do so? I'd imagine very similarly to how Johan wrote it.

 What makes you think LDC can't optimize out the check if there's a 
 better way? Then the check is there in case the optimizer you are 
 dealing with is going to call an opaque memcmp in all cases.
That actually is irrelevant. Whether it gets inlined, whether even it's loop is unrolled by the compiler - that is all beside the point. If you hardcode the check in the library, that check is there for everyone using that library. On all hardware and for all data sizes. Irrespective of whether it can, on a given platform with a given array size, be actually faster to just do the call/loop/etc. than to do a check first. Irrespective of what a given compiler is capable of. There cannot be a universal optimization here. Users can always write a compare_arrays_ptrcheck if so required, but they cannot "unwrite" druntime.
I'm saying the compiler can unwrite druntime, if it knows a better way. Happens all the time with LDC, it will remove loops that it knows don't do anything. And the upside is that compilers that don't do the "smarter" thing will not needlessly call memcmp. -Steve
Jun 02
parent reply Stanislav Blinov <stanislav.blinov gmail.com> writes:
On Wednesday, 3 June 2020 at 00:04:43 UTC, Steven Schveighoffer 
wrote:

 Users can always write a compare_arrays_ptrcheck if so 
 required, but they cannot "unwrite" druntime.
I'm saying the compiler can unwrite druntime, if it knows a better way. Happens all the time with LDC, it will remove loops that it knows don't do anything. And the upside is that compilers that don't do the "smarter" thing will not needlessly call memcmp.
...Yes? And that will fall under a hypothetical case when the check just gets removed (or heck, inserted if it's faster). Leaving it in for all other cases when the compiler *can't* remove it. Make the best case better but the worst case worse? No thanks. For the third time, and let me be a little more explicit this time - if a program gives memcmp identical pointers so much as to warrant a test (which is found out by measuring) - the program is doing something wrong. *It* should do a test and not bother with memcmp at all. Or its logic needs to change so as to not have this problem in the first place. Same translates onto druntime's arrays. There's no definitive answer to Johan's original question. It depends. On hardware. On data. Therefore, that check shouldn't be there, it should be delegated to someone capable of making such decision - to the user.
Jun 02
parent reply Steven Schveighoffer <schveiguy gmail.com> writes:
On 6/2/20 8:35 PM, Stanislav Blinov wrote:
 On Wednesday, 3 June 2020 at 00:04:43 UTC, Steven Schveighoffer wrote:
 
 Users can always write a compare_arrays_ptrcheck if so required, but 
 they cannot "unwrite" druntime.
I'm saying the compiler can unwrite druntime, if it knows a better way. Happens all the time with LDC, it will remove loops that it knows don't do anything. And the upside is that compilers that don't do the "smarter" thing will not needlessly call memcmp.
....Yes? And that will fall under a hypothetical case when the check just gets removed (or heck, inserted if it's faster). Leaving it in for all other cases when the compiler *can't* remove it. Make the best case better but the worst case worse? No thanks.
The worst case is opaque memcmp is called in all cases. No thanks. I'll take a few extra cycles over that any day. -Steve
Jun 02
parent Stanislav Blinov <stanislav.blinov gmail.com> writes:
On Wednesday, 3 June 2020 at 01:10:55 UTC, Steven Schveighoffer 
wrote:

 ....Yes? And that will fall under a hypothetical case when the 
 check just gets removed (or heck, inserted if it's faster). 
 Leaving it in for all other cases when the compiler *can't* 
 remove it. Make the best case better but the worst case worse? 
 No thanks.
The worst case is opaque memcmp is called in all cases. No thanks. I'll take a few extra cycles over that any day.
With the check in place, the worst case would be a useless comparison plus the memcmp, or a failed branch on the off chance that you do try to compare identical ranges. Or a useless comparison and a failed branch + memcmp. Depends on your program. Whether the effect would be significant or immeasurable - also depends on your program, and your data, and your hardware. "I'm not sure what my program is doing, so let's make everyone else pay for it". That's what including that test, in memcmp or in druntime, effectively would be.
Jun 02
prev sibling next sibling parent reply Steven Schveighoffer <schveiguy gmail.com> writes:
On 6/2/20 3:38 PM, Johan wrote:
 Hi all,
    I thought that we optimized dynamic array comparison with a check to 
 see if the pointers are equal, but I don't see it in our array 
 comparison implementation in druntime. Quick checking of glibc memcmp 
 also showed that there is no short circuit for when the pointers of the 
 slices are equal.
 
 I was expecting something like:
 ```
    if ( sizes are not equal )
       return false;
    if ( pointers are equal  )
       return true;
    return memcmp;
 ```
 
 I am surprised that memcmp itself does not implement the pointers are 
 equal check. Is there a big impact of adding the shortcircuit check to 
 prevent scanning memory?
 
I thought I remembered this being true, but maybe it was for class instances? Looking back in history, it seems prior to 2017, it was done by the compiler generating the code instead of a template, but seems like it did not include the pointer check. -Steve
Jun 02
parent reply Jonathan M Davis <newsgroup.d jmdavisprog.com> writes:
On Tuesday, June 2, 2020 3:18:40 PM MDT Steven Schveighoffer via Digitalmars-d 
wrote:
 On 6/2/20 3:38 PM, Johan wrote:
 Hi all,

    I thought that we optimized dynamic array comparison with a check to

 see if the pointers are equal, but I don't see it in our array
 comparison implementation in druntime. Quick checking of glibc memcmp
 also showed that there is no short circuit for when the pointers of the
 slices are equal.

 I was expecting something like:
 ```

    if ( sizes are not equal )
       return false;
    if ( pointers are equal  )
       return true;
    return memcmp;

 ```

 I am surprised that memcmp itself does not implement the pointers are
 equal check. Is there a big impact of adding the shortcircuit check to
 prevent scanning memory?
I thought I remembered this being true, but maybe it was for class instances? Looking back in history, it seems prior to 2017, it was done by the compiler generating the code instead of a template, but seems like it did not include the pointer check.
The free function opEquals for classes does check the references first and has for years (as well doing checks like whether either reference is null). I've never looked at what the array implementation does though. - Jonathna M Davis
Jun 02
parent Steven Schveighoffer <schveiguy gmail.com> writes:
On 6/2/20 6:48 PM, Jonathan M Davis wrote:
 On Tuesday, June 2, 2020 3:18:40 PM MDT Steven Schveighoffer via Digitalmars-d
 wrote:
 I thought I remembered this being true, but maybe it was for class
 instances? Looking back in history, it seems prior to 2017, it was done
 by the compiler generating the code instead of a template, but seems
 like it did not include the pointer check.
The free function opEquals for classes does check the references first and has for years (as well doing checks like whether either reference is null). I've never looked at what the array implementation does though.
Sorry, to be clear I meant the array implementation prior to 2017 implemented opEquals by generating code with the compiler. After that, it used the linked template. -Steve
Jun 02
prev sibling next sibling parent reply Dominikus Dittes Scherkl <dominikus scherkl.de> writes:
On Tuesday, 2 June 2020 at 19:38:04 UTC, Johan wrote:
 Hi all,
   I thought that we optimized dynamic array comparison with a 
 check to see if the pointers are equal, but I don't see it in 
 our array comparison implementation in druntime. Quick checking 
 of glibc memcmp also showed that there is no short circuit for 
 when the pointers of the slices are equal.

 I was expecting something like:
 ```
   if ( sizes are not equal )
      return false;
   if ( pointers are equal  )
      return true;
   return memcmp;
 ```

 I am surprised that memcmp itself does not implement the 
 pointers are equal check.
I also would expect this kind of optimization in memcmp and not in the functions using it. Anything at higher level should be unaware of pointers wherever possible. And how do you know this optimization is NOT in memcmp? It's extern C and the source may be not available - have you examined it? There are many implementations of memcmp available - maybe on you're platform the cost for this extra check is too high? (especially given the very low probability that it is ever called with src==dst).
Jun 02
next sibling parent reply Johan <j j.nl> writes:
On Tuesday, 2 June 2020 at 21:27:44 UTC, Dominikus Dittes Scherkl 
wrote:
 On Tuesday, 2 June 2020 at 19:38:04 UTC, Johan wrote:
 Hi all,
   I thought that we optimized dynamic array comparison with a 
 check to see if the pointers are equal, but I don't see it in 
 our array comparison implementation in druntime. Quick 
 checking of glibc memcmp also showed that there is no short 
 circuit for when the pointers of the slices are equal.

 I was expecting something like:
 ```
   if ( sizes are not equal )
      return false;
   if ( pointers are equal  )
      return true;
   return memcmp;
 ```

 I am surprised that memcmp itself does not implement the 
 pointers are equal check.
I also would expect this kind of optimization in memcmp and not in the functions using it. Anything at higher level should be unaware of pointers wherever possible.
Pointers are nothing to be scared of.
 And how do you know this optimization is NOT in memcmp? It's 
 extern C and the source may be not available - have you 
 examined it?
That's what I wrote, yes.
 There are many implementations of memcmp available - maybe on 
 you're platform the cost for this extra check is too high? 
 (especially given the very low probability that it is ever 
 called with src==dst).
glibc is a very commonly used library for memcmp. It does many other checks before starting the comparison (e.g. optimizing for pointer alignment), so the cost of the extra check is perhaps not even measurable. -Johan
Jun 02
parent NaN <divide by.zero> writes:
On Tuesday, 2 June 2020 at 22:05:06 UTC, Johan wrote:
 On Tuesday, 2 June 2020 at 21:27:44 UTC, Dominikus Dittes 
 Scherkl wrote:

 glibc is a very commonly used library for memcmp. It does many 
 other checks before starting the comparison (e.g. optimizing 
 for pointer alignment), so the cost of the extra check is 
 perhaps not even measurable.
Getting two pointers to the same memory location may be such a rare occurrence that it's not worth having the check for it. IE, Adding a tiny overhead on 1000 calls can still cost more than a very large overhead on 1 call.
Jun 02
prev sibling parent Stanislav Blinov <stanislav.blinov gmail.com> writes:
On Tuesday, 2 June 2020 at 21:27:44 UTC, Dominikus Dittes Scherkl 
wrote:

 I also would expect this kind of optimization in memcmp and not 
 in the functions using it. Anything at higher level should be 
 unaware of pointers wherever possible.
How do you pass pointers to memcmp if you're not aware of them? ;)
Jun 02
prev sibling parent reply Patrick Schluter <Patrick.Schluter bbox.fr> writes:
On Tuesday, 2 June 2020 at 19:38:04 UTC, Johan wrote:
 Hi all,
   I thought that we optimized dynamic array comparison with a 
 check to see if the pointers are equal, but I don't see it in 
 our array comparison implementation in druntime. Quick checking 
 of glibc memcmp also showed that there is no short circuit for 
 when the pointers of the slices are equal.

 I was expecting something like:
 ```
   if ( sizes are not equal )
      return false;
   if ( pointers are equal  )
      return true;
   return memcmp;
 ```

 I am surprised that memcmp itself does not implement the 
 pointers are equal check. Is there a big impact of adding the 
 shortcircuit check to prevent scanning memory?
memcmp() doesn't implement the check to avoid memcmp(NULL, NULL, length) returning with 0 instead of segfaulting as it does if any of the 2 pointers in NULL. It's a case of consistant behaviour, either you tolerate NULL pointers in all cases or you segfault in all cases.
Jun 02
next sibling parent Patrick Schluter <Patrick.Schluter bbox.fr> writes:
On Wednesday, 3 June 2020 at 05:48:56 UTC, Patrick Schluter wrote:
 On Tuesday, 2 June 2020 at 19:38:04 UTC, Johan wrote:
 [...]
memcmp() doesn't implement the check to avoid memcmp(NULL, NULL, length) returning with 0 instead of segfaulting as it does if any of the 2 pointers in NULL. It's a case of consistant behaviour, either you tolerate NULL pointers in all cases or you segfault in all cases.
https://stackoverflow.com/questions/16362925/can-i-pass-a-null-pointer-to-memcmp
Jun 02
prev sibling next sibling parent Johan <j j.nl> writes:
On Wednesday, 3 June 2020 at 05:48:56 UTC, Patrick Schluter wrote:
 On Tuesday, 2 June 2020 at 19:38:04 UTC, Johan wrote:
 I am surprised that memcmp itself does not implement the 
 pointers are equal check. Is there a big impact of adding the 
 shortcircuit check to prevent scanning memory?
memcmp() doesn't implement the check to avoid memcmp(NULL, NULL, length) returning with 0 instead of segfaulting as it does if any of the 2 pointers in NULL. It's a case of consistant behaviour, either you tolerate NULL pointers in all cases or you segfault in all cases.
Interesting argument! But "undefined behavior" does not mean the program has to segfault. It's perfectly fine to return 0 for the UB case. -Johan
Jun 03
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 6/3/20 1:48 AM, Patrick Schluter wrote:
 On Tuesday, 2 June 2020 at 19:38:04 UTC, Johan wrote:
 Hi all,
   I thought that we optimized dynamic array comparison with a check to 
 see if the pointers are equal, but I don't see it in our array 
 comparison implementation in druntime. Quick checking of glibc memcmp 
 also showed that there is no short circuit for when the pointers of 
 the slices are equal.

 I was expecting something like:
 ```
   if ( sizes are not equal )
      return false;
   if ( pointers are equal  )
      return true;
   return memcmp;
 ```

 I am surprised that memcmp itself does not implement the pointers are 
 equal check. Is there a big impact of adding the shortcircuit check to 
 prevent scanning memory?
memcmp() doesn't implement the check to avoid memcmp(NULL, NULL, length) returning with 0 instead of segfaulting as it does if any of the 2 pointers in NULL. It's a case of consistant behaviour, either you tolerate NULL pointers in all cases or you segfault in all cases.
Affirmative: https://code.woboq.org/userspace/glibc/string/memcmp.c.html#301 My take on the original matter is - adding an easily-predictable branch is unlikely to affect speed in the most naive speculative execution hardware. However, prediction does take resources that would be otherwise available for other branches, and the branch adds to code size. Both of these are important in large applications. So inserting a test will look good in microbenchmarks but may be actually a negative in real-world use.
Jun 03
parent Johan <j j.nl> writes:
On Wednesday, 3 June 2020 at 13:46:00 UTC, Andrei Alexandrescu 
wrote:
 On 6/3/20 1:48 AM, Patrick Schluter wrote:
 On Tuesday, 2 June 2020 at 19:38:04 UTC, Johan wrote:
 I am surprised that memcmp itself does not implement the 
 pointers are equal check. Is there a big impact of adding the 
 shortcircuit check to prevent scanning memory?
memcmp() doesn't implement the check to avoid memcmp(NULL, NULL, length) returning with 0 instead of segfaulting as it does if any of the 2 pointers in NULL. It's a case of consistant behaviour, either you tolerate NULL pointers in all cases or you segfault in all cases.
Affirmative: https://code.woboq.org/userspace/glibc/string/memcmp.c.html#301 My take on the original matter is - adding an easily-predictable branch is unlikely to affect speed in the most naive speculative execution hardware. However, prediction does take resources that would be otherwise available for other branches, and the branch adds to code size. Both of these are important in large applications. So inserting a test will look good in microbenchmarks but may be actually a negative in real-world use.
It's such a simple optimization idea that I think it must have been tested by many many people already; presumably the outcome was that the gain is not worth the cost. In case the data is _not_ equal, I guess the inequality actually shows up quite early so only a fraction of memory is scanned. In case the data _is_ equal, that's where pointer comparison can cut a significant amount of memory read, but perhaps in most cases the data being equal is still stored in different memory locations. Again, I'm very interested to see a perf comparison in a real application. Perhaps I can test this at Weka. -Johan
Jun 03