On 8 April 2012 12:54, Manu <turkeyman@gmail.com> wrote:

> 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?
>

The only way I can see this working is if the marker happens to be the top bit of the size (limiting arrays to 2gb on 32bit systems, which is probably fine), and if set, the next 7 bits are the size, leaving 7 bytes for a string... 7 bytes is pushing it, 15 bytes is very useful, 7 is borderline...

That all said, I'll ultimately end out with my own string type anyway which is multiples of, and aligned to 16 bytes, which will support SSE string opcodes. I wonder if these considerations can be factored into the built-in string?

Is it realistic that anyone can actually use raw d-string's in an app that
performs a lot of string manipulation? I bet most people end up with a
custom string class anyway...
Who's written a string-heavy app without their own string helper class? I
ended up with a string class within about half an hour of trying to work
with D strings (initially just to support stack strings, then it grew).

On 4/8/12 1:33 AM, Daniel Murphy wrote:
> - This has been a disaster for AAs

Making them "magic" has been the problem. We must revert that.

> - Is it worth doing for 32 bit?

Probably not.

> - Would generate false pointers

Fair point but we're also moving to precise collection :o).

> - Run-time check on every array access?

Cost is negligible in most cases according to the extensive measurements we've done.

> - Why should this be in the language/compiler instead of phobos?

People use built-in immutable(char)[] as strings. We want to benefit existing uses.


Andrei

On 4/8/12 4:30 AM, Andrej Mitrovic wrote:
> 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

Walter and I agree that relying on sheer D for instead of compiler-generated magic (in this case, bitmaps etc) is the better solution. Implementing a generic marker as a template using introspection is very simple - I predict a few dozen lines. Once that is finished there will obviously be no template errors. I don't know whether build times would be impacted. There will be fewer ICEs because there will be less reliance on the compiler.

Andrei

On 4/8/12 4:46 AM, 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.

Hehe. Good idea. On big endian machines the last byte is the ticket!

Andrei

On 4/8/12 9:49 AM, Andrei Alexandrescu wrote:
> On 4/8/12 4:46 AM, 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.
>
> Hehe. Good idea. On big endian machines the last byte is the ticket!

s/big/little/

On 4/8/12 4:54 AM, Manu wrote:
> On 8 April 2012 12:46, Vladimir Panteleev <vladimir@thecybershadow.net
> <mailto: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?

We can experiment with making strings shorter than 8 chars in-situ. The drawback will be that length will be limited to 29 bits, i.e. 512MB.

Andrei

On 4/8/12 4:55 AM, Vladimir Panteleev wrote:
> 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.

Me too, actually.

> 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...)

It's amazing how fast shift works :o).

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

Once anyone asks for .ptr a conservative copy will be made.


Andrei

On 4/8/12 5:45 AM, Jacob Carlborg wrote:
> 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.

The mistake with AAs was done long ago, but it was forced as AAs predated templates.

Andrei

On 2012-04-08 05:56:38 +0000, Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> said:

> 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.

Small buffer optimization is a very good thing to have indeed. But… how can you preserve existing semantics? For instance, let's say you have this:

	string s = "abcd";

which is easily representable as a small string. Do you use the small buffer optimization in the assignment? That seems like a definitive yes.

But as soon as you take a pointer to that string, you break the immutability guaranty:

	immutable(char)[] s = "abcd";
	immutable(char)* p = s.ptr;
	s = "defg"; // assigns to where?

There's also the issue of this code being legal currently:

	immutable(char)* getPtr(string s) {
		return s.ptr;
	}

If you pass a small string to getPtr, it'll be copied to the local stack frame and you'll be returning a pointer to that local copy.

You could mitigate this by throwing an error when trying to get the pointer to a small string, but then you have to disallow taking the pointer of a const(char)[] pointing to it:

	const(char)* getPtr2(const(char)[] s) {
		return s.ptr;
	}

	const(char)* getAbcdPtr() {
		string s = "abcd";
	
		// s implicitly converted to regular const(char)[] pointing to local stack frame
		const(char)* c = getPtr2(s);

		// c points to the storage of s, which is the local stack frame
		return c;
	}

So it's sad, but I am of the opinion that the only way to implement small buffer optimization is to have a higher-level abstraction, a distinct type for such small strings.


-- 
Michel Fortin
michel.fortin@michelf.com
http://michelf.com/

On 4/8/12 8:54 AM, H. S. Teoh wrote:
> 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

Thanks for the update! Let me reiterate this is important work for many reasons, so it would be great if you got around to pushing it through. Do you think someone else in the community could help you?

Andrei