Mantis Bug Tracker

View Issue Details Jump to Notes ] Issue History ] Print ]
IDProjectCategoryView StatusDate SubmittedLast Update
0004965OCamlOCaml generalpublic2010-01-25 17:012013-03-31 00:20
Reportermottl 
Assigned Toshinwell 
PrioritynormalSeverityminorReproducibilityalways
StatusresolvedResolutionfixed 
PlatformOSOS Version
Product Version3.11.2 
Target VersionFixed in Version4.00.0 
Summary0004965: String.compare not specialized
DescriptionUnlike 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.
TagsNo tags attached.
Attached Files

- Relationships

-  Notes
(0005233)
mottl (reporter)
2010-01-27 15:38

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
(0005278)
shinwell (developer)
2010-03-30 14:20

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.
(0005279)
mottl (reporter)
2010-03-30 15:58

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.
(0005280)
shinwell (developer)
2010-03-30 16:02

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.
(0007867)
xleroy (administrator)
2012-08-02 09:35

I don't know when this PR was addressed, but as of release 4.00, String.compare does call caml_string_compare.

- Issue History
Date Modified Username Field Change
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 =>


Copyright © 2000 - 2011 MantisBT Group
Powered by Mantis Bugtracker