[Vm-dev] Immediates

Eliot Miranda eliot.miranda at gmail.com
Thu May 7 17:57:09 UTC 2009

On Thu, May 7, 2009 at 10:11 AM, Bert Freudenberg <bert at freudenbergs.de>wrote:

> On 07.05.2009, at 18:53, Eliot Miranda wrote:
> On Thu, May 7, 2009 at 9:36 AM, Igor Stasenko <siguctua at gmail.com> wrote:
>> 2009/5/7 Eliot Miranda <eliot.miranda at gmail.com>:
>> >I intend to add immediate characters within the next few months.
>> >
>> so, does that means that you will extend the oop tag to 2 bits (or more)?
> Yes.  Keep 31-bit SmallIntegers, provide e.g. 24-bit immediate characters.
>  Andreas wrote a thorough sketch of this scheme<http://lists.squeakfoundation.org/pipermail/vm-dev/2006-January/000429.html>in 2006.
>> Or just reserve a non-movable heap space for character objects, like:
>> isCharacterObject: oop
>>  ^ oop >= charsStart and: [ oop < charsEnd ]
> No. This doesn't scale to unicode.  The tagged approach provides much
> faster string access, and identity comparison for all characters, not just
> the byte range.
> Do we have evidence that Character allocation is an actual performance
> bottleneck?

The problem is not so much character allocation because by far the most
character access in e.g. IDE usage is with byte characters. The problem is
character indirection.  To assign a character to a string in
ByteString>>at:put: requires indirecting through the character to extract
the character code.  To answer a character in ByteString>>at: involves
indirecting through the specialObjectsOop to fetch the characterTable and
indexing the character table with the byte character code.  But allocation
is very slow in Squeak so for Unicode the problem for at: is much worse
because we also have to allocate the result box.

This is very slow compared to merely adding/removing a tag bit.  As for
evidence as to whether this is a bottle-neck it is obscured by plugin
primitives that mitigate the effects, such as primitiveFindSubstring.  In
general these are a bad idea because they're hard to debug, effectively
impossible to change and are not polymorphic.  But take a look at the
following, which uses identityIndexOf: to avoid primitive machinery (but is
no slower since invoking the primitive machinery is in itself expensive)

| wa ws ba bs bc wc n |
ba := (120 to: 125) collect: [:cc| Character value: cc].
bs := ba asString.
bc := ba last.
wa := (12345 to: 12350) collect: [:cc| Character value: cc].
ws := wa asString.
wc := wa last.
n := 1000000.
{ Time millisecondsToRun: [1 to: n do: [:ign| ba identityIndexOf: bc
ifAbsent: 0]].
  Time millisecondsToRun: [1 to: n do: [:ign| bs identityIndexOf: bc
ifAbsent: 0]].
  Time millisecondsToRun: [1 to: n do: [:ign| wa identityIndexOf: wc
ifAbsent: 0]].
  Time millisecondsToRun: [1 to: n do: [:ign| ws identityIndexOf: wc
ifAbsent: 0]] }
Squeak 4.0 beta1 Closure: #(448 1058 451 8631)
Stack VM: #(581 1531 579 7303)
Cog: #(214 600 213 1970)

So string access is two to three times slower than array access when the
result is fetched from the character table and an order of magnitude worse
when the result must be boxed.  (I don't know why the Stack VM is slower
than Squeak 4 for non-boxed access; I probably need to do a merge :) ).

>  - Bert -
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.squeakfoundation.org/pipermail/vm-dev/attachments/20090507/c2855667/attachment.htm

More information about the Vm-dev mailing list