On 4/9/12 3:24 AM, Don wrote:
> On 08.04.2012 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:
>
> vote -= real.infinity.
>
> That would kill D.

Why?

Andrei

On Sun, 08 Apr 2012 01:56:38 -0400, Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> 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.
>
> 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?

No, this would suck.

A better solution - make an *actual* string type that does this, and fixes all the shitty problems that we have from shoehorning arrays into UTF strings.  Then alias that type to string.

I'm so sick of phobos trying to pretend char[] is not an array, and this would just be another mark against D.

-Steve

On 4/9/12 4:21 AM, Manu wrote:
> After thinking on it a bit, I'm becoming a little worried about this
> move for 2 rarely considered reasons:
> Using lowering to a template, debug(/unoptimised) performance will
> probably get a lot slower, which is really annoying. And
> debugging/stepping might become considerably more annoying too, if every
> time I press F11 (step in) over a function call that happens to receive
> an arg from an array, the debugger then steps into the array templates
> index operator... We'd be no better off than with STL, unless the
> language has clever ways of hiding this magic from the debugger too, and
> optimising/inlining the index even in debug builds...? But this is the
> built-in array, and not a library we can optionally not use.

I agree. So we have the counterarguments:

1. Lowering would treat array primitives as sheer D code, subject to refusal of inlining. That means worse performance.

2. Unless the compiler takes special measures, source-level debuggers will trace through core, uninteresting code for array operations.

3. There are patterns that attempt to optimize by e.g. using .ptr, but end up pessimizing code because they trigger multiple memory allocations.


Andrei

On Monday, 9 April 2012 at 14:55:16 UTC, Andrei Alexandrescu wrote:
> 3. There are patterns that attempt to optimize by e.g. using .ptr, but end up pessimizing code because they trigger multiple memory allocations.
>
>
> Andrei

It's important to note that this pattern is probably most common in glue code to C libraries, not bounds-checking related optimizations. There are countless of C library functions which receive the equivalent of an array by taking a pointer and a length, and implicit allocation on `foo.ptr` is completely unacceptable in these cases.

It's also common to avoid the `toStringz` function for strings you know are zero-terminated, using `.ptr` directly instead, as the toStringz function unconditionally appends a zero these days (and for good reasons, its previous optimization was extremely optimistic about its input).

On 4/9/12, Jakob Ovrum <jakobovrum@gmail.com> wrote:
> It's also common to avoid the `toStringz` function for strings you know are zero-terminated, using `.ptr` directly instead.

Yup. E.g. WinAPI text drawing functions take a wchar* and a length. I don't have to call toUTF16z but just pass a pointer, or even a pointer to a specific element via &arr[index] (after calling std.utf.stride, of course).

> the toStringz function unconditionally appends a zero these days

The one taking (const(char)[] s) does this, but not the other overload
taking (string s). Whether or not that's safe I don't really know.
I've had an argument over this on github, but I don't know if it was
about toStringz or maybe toUTF16z. I haven't got the link to the
discussion.

On Monday, 9 April 2012 at 15:37:37 UTC, Andrej Mitrovic wrote:
> On 4/9/12, Jakob Ovrum <jakobovrum@gmail.com> wrote:
> The one taking (const(char)[] s) does this, but not the other overload
> taking (string s). Whether or not that's safe I don't really know.
> I've had an argument over this on github, but I don't know if it was
> about toStringz or maybe toUTF16z. I haven't got the link to the
> discussion.

You're right, I just confirmed the optimization is still in place for the `string` version. The documentation is identical for both functions. I think this is a mistake.

It assumes that the string is either a compiler-generated literal or a GC allocated string, while the documentation does not mention such assumptions. With all the focus on manual memory management and pluggable allocators going on, I think the optimization must be removed or the documentation for the `string` overload changed.

This optimization can always be put back in without narrowing the scope of the `string` overload once the above conditions can be reliably checked.

Another option is to add a known-bug section to the `string` overload informing users that the function may fail on custom-allocated strings.

On 4/9/12, Jakob Ovrum <jakobovrum@gmail.com> wrote:
> With all the focus on manual memory
> management and pluggable allocators going on, I think the
> optimization must be removed or the documentation for the
> `string` overload changed.

Or add a compile-time argument:
toStringz(bool ForceAllocate = true)(string s)

Or split the unsafe version into another function.

On 9 April 2012 17:55, Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org>wrote:

> On 4/9/12 4:21 AM, Manu wrote:
>
>> After thinking on it a bit, I'm becoming a little worried about this
>> move for 2 rarely considered reasons:
>> Using lowering to a template, debug(/unoptimised) performance will
>> probably get a lot slower, which is really annoying. And
>> debugging/stepping might become considerably more annoying too, if every
>> time I press F11 (step in) over a function call that happens to receive
>> an arg from an array, the debugger then steps into the array templates
>> index operator... We'd be no better off than with STL, unless the
>> language has clever ways of hiding this magic from the debugger too, and
>> optimising/inlining the index even in debug builds...? But this is the
>> built-in array, and not a library we can optionally not use.
>>
>
> I agree. So we have the counterarguments:
>
> 1. Lowering would treat array primitives as sheer D code, subject to refusal of inlining. That means worse performance.
>
> 2. Unless the compiler takes special measures, source-level debuggers will trace through core, uninteresting code for array operations.
>
> 3. There are patterns that attempt to optimize by e.g. using .ptr, but end up pessimizing code because they trigger multiple memory allocations.


Indeed. I don't think the small array optimisation would benefit us in any
way that could even come close to balancing the loss. I don't think it
would benefit us much at all regardless, since we've already proven the
need for a string class anyway, and we can make such small-string
optimisations already.
I am very wary of removing a fundamental language primitive, that is, the
basic ability to express an array with absolutely no frills.

This idea only really benefits utf-8 strings, so why not just make a real
d-string class in phobos and be done with it? People complain about UTF
issues with raw strings, and this is what you intend to do anyway to
implement the optimisation.
d-string could perhaps be made to appear as a first-class language feature
via the 'string' keyword, and lower to the library in the way you describe.
Just don't blanket this across all arrays in general.

"Andrei Alexandrescu" <SeeWebsiteForEmail@erdani.org> wrote in message news:jlut8k$j4o$1@digitalmars.com...
>
> I agree. So we have the counterarguments:
>
> 1. Lowering would treat array primitives as sheer D code, subject to refusal of inlining. That means worse performance.
>

So in other words, we need the @forceinline that some people have strongly requested? Make it work even without -inline, and then add -noinline for any rare cases where someone might need to forcefully disable @forceinline. Shouldn't that take care of it?

> 2. Unless the compiler takes special measures, source-level debuggers will trace through core, uninteresting code for array operations.
>

Would @forceinline fix this?

> 3. There are patterns that attempt to optimize by e.g. using .ptr, but end up pessimizing code because they trigger multiple memory allocations.

Someone's suggestion of just making .ptr null instead of doing implicit allocations was an interesting idea.

On 04/10/12 07:01, Nick Sabalausky wrote:
> "Andrei Alexandrescu" <SeeWebsiteForEmail@erdani.org> wrote in message news:jlut8k$j4o$1@digitalmars.com...
>>
>> I agree. So we have the counterarguments:
>>
>> 1. Lowering would treat array primitives as sheer D code, subject to refusal of inlining. That means worse performance.
>>
> 
> So in other words, we need the @forceinline that some people have strongly requested? Make it work even without -inline, and then add -noinline for any rare cases where someone might need to forcefully disable @forceinline. Shouldn't that take care of it?

Obviously, yes, but should wait until enough attribute support is in place and not be just a @inline hack (no point in naming it forceinline - there's no other kind of inline).

>> 2. Unless the compiler takes special measures, source-level debuggers will trace through core, uninteresting code for array operations.
>>
> 
> Would @forceinline fix this?

No, but the compiler could just omit the debuginfo for the lowerings, unless requested with a flag.

>> 3. There are patterns that attempt to optimize by e.g. using .ptr, but end up pessimizing code because they trigger multiple memory allocations.
> 
> Someone's suggestion of just making .ptr null instead of doing implicit allocations was an interesting idea.

I hope that wasn't a serious suggestion. What might be possible is passing
strings by reference and atomically changing the representation when (if) a
pointer is needed. That would have problems too (ABI change, can't have RO
strings, can't keep the small strings in registers etc).
Doing the small buffer optimization for a new type may be possible, but trying
to add it to the current char[] arrays is probably not a good idea.

artur