String comparison primitive preliminary speed-up result: 20-600x

 

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

Ref. blog post, are you sure you are measuring equivalent entities?
Usually the AsciiOrder is a constant, preallocated array, no?

Seems to me, with the code posted in blog post, you're mostly measuring
array instantation, not collate...

var := ByteString new: 3.

 [ByteString compare: var with: var collated: (0 to: 255) asByteArray]
benchFor: 5 second.
a BenchmarkResult(500,460 iterations in 5 seconds 1 millisecond. 100,072 per
second)

AsciiCollate := (0 to: 255) asByteArray.

 [ByteString compare: var with: var collated: AsciiCollate] benchFor: 5
second.

a BenchmarkResult(79,507,782 iterations in 5 seconds 2 milliseconds.
15,895,198 per second)



--
Sent from: http://forum.world.st/Squeak-VM-f104410.html

Right I knew something was off.

Let me patch this.

On Wed, Feb 21, 2018 at 3:00 PM, Henrik Sperre Johansen <[hidden email]> wrote:

Ref. blog post, are you sure you are measuring equivalent entities?
Usually the AsciiOrder is a constant, preallocated array, no?

Seems to me, with the code posted in blog post, you're mostly measuring
array instantation, not collate...

var := ByteString new: 3.

 [ByteString compare: var with: var collated: (0 to: 255) asByteArray]
benchFor: 5 second.
a BenchmarkResult(500,460 iterations in 5 seconds 1 millisecond. 100,072 per
second)

AsciiCollate := (0 to: 255) asByteArray.

 [ByteString compare: var with: var collated: AsciiCollate] benchFor: 5
second.

a BenchmarkResult(79,507,782 iterations in 5 seconds 2 milliseconds.
15,895,198 per second)



--
Sent from: http://forum.world.st/Squeak-VM-f104410.html

--

Clément Béra

Pharo consortium engineer

https://clementbera.wordpress.com/

Bâtiment B 40, avenue Halley 59650 Villeneuve d'Ascq