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

"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!!

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

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.

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?

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.

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

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.

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;

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.