0004965: String.compare not specialized

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 =>

Relationships