[Vm-dev] String comparison primitive preliminary speed-up result: 20-600x

Clément Bera bera.clement at gmail.com
Wed Feb 21 10:33:45 UTC 2018


Hi all,

*The short version:*

After looking into MiscPlugin with Eliot, we decided to work on a numbered
primitive to speed up String comparison especially String>>#= (which
matters for parsers that are widely used by our communities) as a long-term
replacement for compare:with:collated: Misc primitive. Being numbered
allows the JIT to have an entry for it. We (likely Eliot) will work on
other Misc primitives to compile them differently in the future (No
Smalltalk level smart syntax to ease cross language management) but aside
from String comparison, they will remain in a plugin, since they're not as
critical.

The new primitive is as follow (optional last parameter so 2 versions):
ByteString >> *compareWith:* anotherString
ByteString >> *compareWith:* anotherString *collated:* order
"Return a negative Smi, 0 or a positive Smi if self is < = or  > to
anotherString, with the collating order of characters given optionally by
the order array."

Preliminary benchmarks show 20 to 600x speed-up in String comparison (< <=
= > >= on Strings; 600x on small strings, 20x on large strings). String
comparison does not use any more the optional last parameter, only other
APIs do. Sophie in CC did the bulk of the work as part of a 100h student
project, though various discussion in the mailing list involving many of us
but especially Levente, Eliot and me helped a lot. There are still some
tests to write to make sure everything is stable before integration, but my
understanding is that integration should happen anytime soon. Sophie, could
you please answer a time frame for integration to this mail?

*The long version:*

The blog version includes assembly code, Cog's RTL code & Slang code for
each version as well as the exact preliminary benchmarks we ran:
https://clementbera.wordpress.com/2018/02/17/massive-string-comparison-performance-boost-up-coming-in-the-cog-vm/

Levente maybe you want to review the long version in my blog if you have
comments/advises before integration. I guess you will write accurate
micro-benchmarks once it's integrated anyway.

This LLVM/GCC performance difference is very annoying though for correct
evaluation of speed-ups, I wonder, have any one seen a difference there
before for other primitives? PrimitiveStringReplace might have similar
issues. I don't know if we could report those things as bugs to the LLVM
people somehow.

Best,


-- 
Clément Béra
Pharo consortium engineer
https://clementbera.wordpress.com/
Bâtiment B 40, avenue Halley 59650 Villeneuve d'Ascq
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.squeakfoundation.org/pipermail/vm-dev/attachments/20180221/b39a856f/attachment-0001.html>


More information about the Vm-dev mailing list