|Anonymous | Login | Signup for a new account||2016-10-26 11:26 CEST|
|Main | My View | View Issues | Change Log | Roadmap|
|View Issue Details|
|ID||Project||Category||View Status||Date Submitted||Last Update|
|0004965||OCaml||OCaml general||public||2010-01-25 17:01||2015-07-24 10:39|
|Target Version||Fixed in Version||4.00.0|
|Summary||0004965: String.compare not specialized|
|Description||Unlike e.g. Int32.compare, the String.compare function calls the polymorphic comparison function instead of the one specialized for strings. This can be fixed quickly by adding a type annotation.|
|Tags||No tags attached.|
Btw., it seems that optimizations are not performed even in the presence of type annotations unless the function is eta expanded, i.e. function parameters with type annotations have to be specified explicitly. There doesn't seem to be any good reason why these kinds of optimizations couldn't be done otherwise so we hope this could be fixed, too.
Note that this also extends to the use of higher-order functions. E.g. in this example "compare" will not be optimized to compare integers:
let foo lst = List.fold_left compare 0 lst
But here it will be:
let foo lst = List.fold_left (fun a b -> compare a b) 0 lst
I have done some quick experiments on an x86-64 Intel box and it seems to be marginally slower to add the type annotation and hence use caml_string_compare directly. I think this is probably due to the fact that it uses a different comparison method from compare_val. The former uses memcmp, which on this architecture is I believe expanded by gcc into a repz cmpsb instruction, whereas compare_val uses a simple loop that is not transformed in this way. Do you have performance numbers that indicate any significant performance increase?
I think any optimization in this area that yields anything other than marginal results with high variance across architectures is going to need more careful consideration. One thing that does come to mind is that it might be possible to significantly speed up string _equality_ checking by always padding strings to some boundary (which will admittedly waste a little space) and then using vector instructions to test equality.
I guess the comparison method could then be improved, too. String.compare could be implemented to use the fastest generic function available on a platform. This may not necessarily be the best for most use cases (e.g. small strings), but unless we have a statistical study of what works best for most people, this may be a good start.
Concerning padding: strings always occupy full machine words so equality checking should be trivial. The value header stores the number of words, the last word stores a "correction" to words*word_size in its last byte that needs to be subtracted. Since all OCaml strings are NULL-terminated, this always works out. I think the only thing that may need to be changed to make your proposed equality check work directly is to zero out the last word in the string before setting the correction (in caml_alloc_string). Or just check all words but the last one, and handle that one separately.
|This is still pretty hypothetical, but it might be that you want to use 128-bit vector operations, so the machine word size might not be sufficient for the padding. But you might gain some speedup without going to the full vector width. As regards the contents of the end of the string, I was thinking of having the alloc function zero the last part.|
I don't know when this PR was addressed, but as of release 4.00, String.compare does call caml_string_compare.
|2010-01-25 17:01||mottl||New Issue|
|2010-01-27 15:38||mottl||Note Added: 0005233|
|2010-03-30 14:20||shinwell||Note Added: 0005278|
|2010-03-30 14:20||shinwell||Status||new => assigned|
|2010-03-30 14:20||shinwell||Assigned To||=> shinwell|
|2010-03-30 15:58||mottl||Note Added: 0005279|
|2010-03-30 16:02||shinwell||Note Added: 0005280|
|2012-07-11 13:31||doligez||Target Version||=> 4.01.0+dev|
|2012-07-31 13:36||doligez||Target Version||4.01.0+dev => 4.00.1+dev|
|2012-08-02 09:35||xleroy||Note Added: 0007867|
|2012-08-02 09:35||xleroy||Status||assigned => resolved|
|2012-08-02 09:35||xleroy||Resolution||open => fixed|
|2012-08-02 09:35||xleroy||Fixed in Version||=> 4.00.0|
|2012-08-02 09:35||xleroy||Target Version||4.00.1+dev =>|
|2015-07-24 10:39||xleroy||Status||resolved => closed|
|Copyright © 2000 - 2011 MantisBT Group|