April 08, 2012 Small Buffer Optimization for string and friends | ||||
---|---|---|---|---|
| ||||
Walter and I discussed today about using the small string optimization in string and other arrays of immutable small objects. On 64 bit machines, string occupies 16 bytes. We could use the first byte as discriminator, which means that all strings under 16 chars need no memory allocation at all. It turns out statistically a lot of strings are small. According to a variety of systems we use at Facebook, the small buffer optimization is king - it just works great in all cases. In D that means better speed, better locality, and less garbage. For this to happen, we need to start an effort of migrating built-in arrays into runtime, essentially making them templates that the compiler lowers to. So I have two questions: 1. What happened to the new hash project? We need to take that to completion. 2. Is anyone willing to start the effort of migrating built-in slices into templates? Thanks, Andrei |
April 08, 2012 Re: Small Buffer Optimization for string and friends | ||||
---|---|---|---|---|
| ||||
Posted in reply to Andrei Alexandrescu | "Andrei Alexandrescu" <SeeWebsiteForEmail@erdani.org> wrote in message news:jlr9ak$28bv$1@digitalmars.com... > Walter and I discussed today about using the small string optimization in string and other arrays of immutable small objects. > > On 64 bit machines, string occupies 16 bytes. We could use the first byte as discriminator, which means that all strings under 16 chars need no memory allocation at all. > > It turns out statistically a lot of strings are small. According to a variety of systems we use at Facebook, the small buffer optimization is king - it just works great in all cases. In D that means better speed, better locality, and less garbage. > This sounds like it would be a great addition to phobos. > For this to happen, we need to start an effort of migrating built-in arrays into runtime, essentially making them templates that the compiler lowers to. - This has been a disaster for AAs - Is it worth doing for 32 bit? - Would generate false pointers - Run-time check on every array access? - Why should this be in the language/compiler instead of phobos? April 1st was last week!! |
April 08, 2012 Re: Small Buffer Optimization for string and friends | ||||
---|---|---|---|---|
| ||||
Posted in reply to Andrei Alexandrescu | On 4/8/12, Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> wrote: > essentially making them templates I just hope that doesn't cause: 1) Awful template errors 2) Slower build times 3) More ICEs |
April 08, 2012 Re: Small Buffer Optimization for string and friends | ||||
---|---|---|---|---|
| ||||
Posted in reply to Andrei Alexandrescu | On Sunday, 8 April 2012 at 05:56:36 UTC, Andrei Alexandrescu wrote:
> Walter and I discussed today about using the small string optimization in string and other arrays of immutable small objects.
>
> On 64 bit machines, string occupies 16 bytes. We could use the first byte as discriminator, which means that all strings under 16 chars need no memory allocation at all.
Don't use the first byte. Use the last byte.
The last byte is the highest-order byte of the length. Limiting arrays to 18.37 exabytes, as opposed to 18.45 exabytes, is a much nicer limitation than making assumptions about the memory layout.
|
April 08, 2012 Re: Small Buffer Optimization for string and friends | ||||
---|---|---|---|---|
| ||||
Posted in reply to Vladimir Panteleev Attachments:
| On 8 April 2012 12:46, Vladimir Panteleev <vladimir@thecybershadow.net>wrote: > On Sunday, 8 April 2012 at 05:56:36 UTC, Andrei Alexandrescu wrote: > >> Walter and I discussed today about using the small string optimization in string and other arrays of immutable small objects. >> >> On 64 bit machines, string occupies 16 bytes. We could use the first byte as discriminator, which means that all strings under 16 chars need no memory allocation at all. >> > > Don't use the first byte. Use the last byte. > > The last byte is the highest-order byte of the length. Limiting arrays to 18.37 exabytes, as opposed to 18.45 exabytes, is a much nicer limitation than making assumptions about the memory layout. > What is the plan for 32bit? |
April 08, 2012 Re: Small Buffer Optimization for string and friends | ||||
---|---|---|---|---|
| ||||
Posted in reply to Vladimir Panteleev | On Sunday, 8 April 2012 at 09:46:28 UTC, Vladimir Panteleev wrote:
> On Sunday, 8 April 2012 at 05:56:36 UTC, Andrei Alexandrescu wrote:
>> Walter and I discussed today about using the small string optimization in string and other arrays of immutable small objects.
>>
>> On 64 bit machines, string occupies 16 bytes. We could use the first byte as discriminator, which means that all strings under 16 chars need no memory allocation at all.
>
> Don't use the first byte. Use the last byte.
>
> The last byte is the highest-order byte of the length. Limiting arrays to 18.37 exabytes, as opposed to 18.45 exabytes, is a much nicer limitation than making assumptions about the memory layout.
Erm... never mind, I thought the pointer was the first field.
Even so, how would you use the lowest-order byte of the length as a discriminator? Unless you allocated bytes 2-8 for the length (which would be an unaligned read, or a shift every time...)
"making assumptions about the memory layout" now seems like the only solution.
Also, what will be .ptr for such arrays? It can't point inside the string, because the type is immutable and the array is on the stack. Duplication can be expensive as well.
|
April 08, 2012 Re: Small Buffer Optimization for string and friends | ||||
---|---|---|---|---|
| ||||
Posted in reply to Andrei Alexandrescu | On 2012-04-08 07:56, Andrei Alexandrescu wrote: > For this to happen, we need to start an effort of migrating built-in > arrays into runtime, essentially making them templates that the compiler > lowers to. So I have two questions: Just don't make the same mistake as with AA. -- /Jacob Carlborg |
April 08, 2012 Re: Small Buffer Optimization for string and friends | ||||
---|---|---|---|---|
| ||||
Posted in reply to Andrei Alexandrescu | On Sun, Apr 08, 2012 at 12:56:38AM -0500, Andrei Alexandrescu wrote: [...] > 1. What happened to the new hash project? We need to take that to completion. [...] Sorry, I've been busy at work and haven't had too much free time to work on it. The current code is available on github: https://github.com/quickfur/New-AA-implementation The major outstanding issues are: - Qualified keys not fully working: the current code has a few corner cases that don't work with shared/immutable/inout keys. One major roadblock is how to implement this: alias someType T; inout(T) myFunc(inout(T) arg, ...) { int[inout(T)] aa; ... } The problem is that inout gets carried over into the AA template, which breaks because it instantiates into something that has: struct Slot { hash_t hash; inout(T) key; // <-- this causes a compile error Value value; } Ideally, AA keys should all be stored as immutable inside the AA, and automatically converted to/from the qualified type the user specified. - Template bloat: the current code uses template member functions, and will instantiate a new function for every implicit conversion of input key types. This also depends on IFTI, which has some quirks (compiler bugs) that make the code ugly (e.g., strings and arrays not treated equally by the compiler, requiring hacks to make implicit conversion work). Timon has suggested an alternative way of handling implicit conversions, which I think is better, but I need to take some time to actually implement it. - Static initialization of AA's (AA literals that compile directly into object code). This should be possible in principle, but I've run into what may be a CTFE bug that prevents it from working. - A not-so-major issue is to finish the toHash() implementations for all native types (currently it works for some common key types, but coverage is still incomplete). Once this is done, we can finally get rid of getHash from TypeInfo; UFCS will let us simply write x.toHash() for pretty much any type x. Once these issues are resolved, there remains the major task of actually integrating this code with druntime/dmd. A lot of work is expected on the dmd end, because of the current amount of hacks in dmd to make AA's work. T -- Valentine's Day: an occasion for florists to reach into the wallets of nominal lovers in dire need of being reminded to profess their hypothetical love for their long-forgotten. |
April 08, 2012 Re: Small Buffer Optimization for string and friends | ||||
---|---|---|---|---|
| ||||
Posted in reply to H. S. Teoh | On Sunday, 8 April 2012 at 13:53:07 UTC, H. S. Teoh wrote:
> On Sun, Apr 08, 2012 at 12:56:38AM -0500, Andrei Alexandrescu wrote:
> [...]
>> 1. What happened to the new hash project? We need to take that to
>> completion.
> [...]
>
> Sorry, I've been busy at work and haven't had too much free time to work
> on it. The current code is available on github:
>
> https://github.com/quickfur/New-AA-implementation
>
> The major outstanding issues are:
>
> - Qualified keys not fully working: the current code has a few corner
> cases that don't work with shared/immutable/inout keys. One major
> roadblock is how to implement this:
>
> alias someType T;
> inout(T) myFunc(inout(T) arg, ...) {
> int[inout(T)] aa;
> ...
> }
>
> The problem is that inout gets carried over into the AA template,
> which breaks because it instantiates into something that has:
>
> struct Slot {
> hash_t hash;
> inout(T) key; // <-- this causes a compile error
> Value value;
> }
>
> Ideally, AA keys should all be stored as immutable inside the AA, and
> automatically converted to/from the qualified type the user specified.
>
> - Template bloat: the current code uses template member functions, and
> will instantiate a new function for every implicit conversion of input
> key types. This also depends on IFTI, which has some quirks (compiler
> bugs) that make the code ugly (e.g., strings and arrays not treated
> equally by the compiler, requiring hacks to make implicit conversion
> work). Timon has suggested an alternative way of handling implicit
> conversions, which I think is better, but I need to take some time to
> actually implement it.
>
> - Static initialization of AA's (AA literals that compile directly into
> object code). This should be possible in principle, but I've run into
> what may be a CTFE bug that prevents it from working.
>
> - A not-so-major issue is to finish the toHash() implementations for all
> native types (currently it works for some common key types, but
> coverage is still incomplete). Once this is done, we can finally get
> rid of getHash from TypeInfo; UFCS will let us simply write x.toHash()
> for pretty much any type x.
>
> Once these issues are resolved, there remains the major task of actually
> integrating this code with druntime/dmd. A lot of work is expected on
> the dmd end, because of the current amount of hacks in dmd to make AA's
> work.
>
>
> T
doesn't this work?
immutable std.traits.Unqual!(inout(T)) key;
|
April 08, 2012 Re: Small Buffer Optimization for string and friends | ||||
---|---|---|---|---|
| ||||
Posted in reply to Tove | On Sun, Apr 08, 2012 at 04:11:10PM +0200, Tove wrote: > On Sunday, 8 April 2012 at 13:53:07 UTC, H. S. Teoh wrote: > >On Sun, Apr 08, 2012 at 12:56:38AM -0500, Andrei Alexandrescu > >wrote: > >[...] > >>1. What happened to the new hash project? We need to take that to completion. > >[...] [...] > >The major outstanding issues are: > > > >- Qualified keys not fully working: the current code has a few corner > > cases that don't work with shared/immutable/inout keys. One major > > roadblock is how to implement this: > > > > alias someType T; > > inout(T) myFunc(inout(T) arg, ...) { > > int[inout(T)] aa; > > ... > > } > > > > The problem is that inout gets carried over into the AA template, > > which breaks because it instantiates into something that has: > > > > struct Slot { > > hash_t hash; > > inout(T) key; // <-- this causes a compile error > > Value value; > > } [...] > doesn't this work? > immutable std.traits.Unqual!(inout(T)) key; I suppose so, but the problem is more with the return type of various AA functions. If the user writes int[inout(T)] aa, then he would expect that aa.keys should return inout(T)[]. But the problem here is that this is impossible to express in the current system, because inout has a different meaning when you write it in the AA method, than its meaning in the context of the calling function. For example, this doesn't quite work: struct AA { ... inout(Key) keys() { ... // Problem: inout here doesn't mean what it // means in the context of the caller } } T -- Tech-savvy: euphemism for nerdy. |
Copyright © 1999-2021 by the D Language Foundation