[snip]

>> > 2) Implicit initialization is great. However, it can clearly and easily
> be
>> > demonstrated to be a serious impediment. Given that D is supposed to be
> a
>> > 'systems' language, I humbly suggest that a mechanism be provided to
>> bypass
>> > such nicities when one is prepared to assume full responsibility. For example, there might be a qualifier for variables that disables the automatic initialization (along the lines of the 'auto' qualifier).
>>
>> The solution is improving the optimizer so it can determine when the initialization is redundant. It already does this for most variables, just not for arrays.
> 
> 
> Great!  Will it eliminate initialization for this type of (trivail) usage:
> 
> void A (void delegate (char[]) formatter)
> {
>     char [1024 * 32] workspace;
> 
>     formatter (workspace);
> }
> 
> Because, if not, then the following modification is the sort of (keyword qualifier) thing that would hand control back to the programmer:
> 
> {
>     uninitialized char[1024 * 32] workspace;
> 
>     formatter (workspace);
> }
> 
> That's perhaps not the best name for it, but you get the idea. It's very clear what's going on, it's entirely optional, and the compiler will do exactly what the programmer intends it to do. No under-the-tablecloth-magic required. Oh, and it's easy to grep for. It's just a suggestion.

As a general principle I agree it would be nice to be able to skip
initialization just like it's nice to be able to turn off array-bounds
checking. But in practice (in D) I wonder how often that would pay off.
Allocating a 32K array on the stack is pretty evil, and I wonder how often
that really happens. What C code were you porting that was doing that? I
assume it was allocating such a big array not because it was going to use
it all (as you said only a small portion of the array gets used) but
because the coder was lazy and was trying to avoid worrying about array
bounds errors. As we all know overwriting array bounds invites exploits and
bugs. In D the way I've been coding APIs that take buffers as input is to
take a dynamic array as "a typical size buffer" and if the buffer turns out
to be too small then the function increases the length field of the local
variable which could potentially allocate new GC'ed memory. For example in
std/stream.d there is the function
  char[] readLine(char[] buffer);
which takes an input buffer and fills it with the next line of text from the
stream. If the line fits in the buffer the output array's length is the
number of characters read and the char* is the buffer's char*. If the line
didn't fit then readLine (potentially) allocates a new buffer (just by
increasing the length field of the local copy of the buffer variable) and
returns the char* of the new buffer. The "overflow" buffer is garbage
collected eventually so there isn't any memory leak going on. So in essence
the input buffer is just a suggested buffer for readLine but there is no
guarantee that the buffer will contain the result of the funtion call when
it is done. This approach means you can target your buffers to the typical
usage and avoid array-bounds errors.

"Ben Hinkle" <bhinkle4@juno.com> wrote in message news:cfg7af$2dbv$1@digitaldaemon.com...
> [snip]
>
> >> > 2) Implicit initialization is great. However, it can clearly and
easily
> > be
> >> > demonstrated to be a serious impediment. Given that D is supposed to
be
> > a
> >> > 'systems' language, I humbly suggest that a mechanism be provided to
> >> bypass
> >> > such nicities when one is prepared to assume full responsibility. For example, there might be a qualifier for variables that disables the automatic initialization (along the lines of the 'auto' qualifier).
> >>
> >> The solution is improving the optimizer so it can determine when the initialization is redundant. It already does this for most variables, just not for arrays.
> >
> >
> > Great!  Will it eliminate initialization for this type of (trivail)
usage:
> >
> > void A (void delegate (char[]) formatter)
> > {
> >     char [1024 * 32] workspace;
> >
> >     formatter (workspace);
> > }
> >
> > Because, if not, then the following modification is the sort of (keyword qualifier) thing that would hand control back to the programmer:
> >
> > {
> >     uninitialized char[1024 * 32] workspace;
> >
> >     formatter (workspace);
> > }
> >
> > That's perhaps not the best name for it, but you get the idea. It's very clear what's going on, it's entirely optional, and the compiler will do exactly what the programmer intends it to do. No under-the-tablecloth-magic required. Oh, and it's easy to grep for. It's just a suggestion.
>
> As a general principle I agree it would be nice to be able to skip initialization just like it's nice to be able to turn off array-bounds checking. But in practice (in D) I wonder how often that would pay off. Allocating a 32K array on the stack is pretty evil, and I wonder how often that really happens.

Is allocating a 2K array on the stack equally evil? From the reply to AJ:

2K allocations:
heap:      504
stack[]:   5681
alloca():  57
asm:       10

32K allocations:
heap:      520
stack[]:   8812
alloca():  118
asm:       10

You can see that the 2K array initialization is almost equally obnoxious, compared to the traditional [asm] C/C++ uninitialized approach. The whole point is that here's a scenario where the compiler thinks it knows best, and won't hand over control unless we run rings around it. Perhaps worse, the whole issue is squirrelled away under the covers; you have to dig like a rabbit just to find the culprit.

> What C code were you porting that was doing that? I
> assume it was allocating such a big array not because it was going to use
> it all (as you said only a small portion of the array gets used) but
> because the coder was lazy and was trying to avoid worrying about array
> bounds errors.

Heavy-duty text processing. The coder wasn't being lazy at all, as out-of-bounds conditions are being checked for. The allocated (temporary) workspace is typically used in only a small amounts, but sporadically will get used more fully. The approach taken was apparently "we'll check for end-of-buffer, but if anything exceeds these limits, then it's so beyond the design-specification that it's an error condition". I understand that to be a rather common approach. It's certainly valid, and rather effective. The D approach to this is, " ...you /vill/ pay ze initialization cost, regardless of vot ze design!"

(that is a caricature; no offense intended to anyone)

The existing code simply took advantage of the fact that it's perfectly legitimate, and very fast, to do that kind of thing in C and C++. If D is going to outlaw such approaches then it had better get it down in the "manifesto". However, I didn't realize that D was such an ideological exercise.

<snip>
> it is done. This approach means you can target your buffers to the typical usage and avoid array-bounds errors.

Yes, this is all well and good. But /redesigning/ existing software to suit is just not a solution. While the approach you discuss is perfectly valid, so was the original (given its apparent design scope) since it did not have array-bounds or buffer-overrun conditions. Further, you can't reliably place an extensible buffer on the stack; thus, you are forced to forego the performance benefits of doing so.

This thread is not about a design-methodology issue ~ if it were, nobody would be allowed to use the stack for array allocation, at all! It's a simple issue of the D language not providing the programmer with "accessible" tools to decide what's best. In this particular case it showed up in ported code. There's nothing to say that it won't show up in original D software either.

As you say, Ben; as a general principal, D should (absolutely) permit the skipping of array initialization. The whole default initialization thing is arguably wonderful, but then not providing accessible control over it is akin to tinpot-dictatorship. For example, I will probably resort to assembly to get around this issue: that's not exactly an accessible or acceptable solution, for obvious reasons. I think we can agree on that basic tenet. Your other points are perhaps more about a design philosophy: that's a different ball-game and, applicable or not, unfortunately does not jive with porting existing code.

The optional "keyword qualifier" example (at the top of the page) is likely to be as trivial as one could hope for within the compiler; combined with a little documentation, that would resolve such issues in a pragmatic and considerate manner. Surely that is far simpler than building an optimizer to read the programmers mind?

Or, is there some fundamental ideology at stake here?

Ahem, you're speaking of allocating a *buffer*. A large thing, perhaps used partially. Normally, i would feel somewhat uneasy to do that on the stack - the heap does it quite well, and, well, if there is still a performance problem, a buffer can be cached/shared/whatever, fairly easily. And if i remember correctly, there was some circumstance which could make the OS break if it had to extend the stack by more than 1 page at a time.

The bulk of performance loss from heap allocation comes from many little objects, much more than from a few big ones... So what's the fuss about? Besides, you'd be using it by a pointer anyway.

-eye

"van eeshan" <vanee@hotmail.net> wrote in message news:cfge6g$2g1j$1@digitaldaemon.com...
> Heavy-duty text processing. The coder wasn't being lazy at all, as out-of-bounds conditions are being checked for. The allocated (temporary) workspace is typically used in only a small amounts, but sporadically will get used more fully. The approach taken was apparently "we'll check for end-of-buffer, but if anything exceeds these limits, then it's so beyond
the
> design-specification that it's an error condition". I understand that to
be
> a rather common approach. It's certainly valid, and rather effective. The
D
> approach to this is, " ...you /vill/ pay ze initialization cost,
regardless
> of vot ze design!"

Here's an example of an alternate way to do it, for code that would typically use only a small amount, but occaisionally could use a great deal. It can also be set up to never overflow (at least until all memory is exhausted) by repeatedly resizing it. This has the advantage of not needing to set up any error recovery, or create and document an error message for the limits.

import std.stdio;

char[] formatter(char[] s)
{
    if (s.length < 14)        // if our passed buffer isn't big enough
        s.length = 14;        // yes, we can reallocate things that were
originally on the stack
    s[0..14] = "abcdefghijklmn";    // copy result into s[]
    return s;
}


void main()
{   char[4] workspace;    // assume 4 is size typically needed in
formatter()
    char[] s;

    s = formatter(workspace);
    writefln(s);
}

"Walter" <newshound@digitalmars.com> wrote ...
> Here's an example of an alternate way to do it, for code that would typically use only a small amount, but occaisionally could use a great
deal.

Thanks Walter, for the alternate implementation. Ben had already suggested that, and I am aware of various other approaches too.

However, let's not confuse this topic with that of design-methodology. As was noted (in the post you replied to) this is a port. Do you think it reasonable to state, " ... Now listen up you ...scurrilous ... miserable bunch of C coders! If you want to join the D party, then you're gonna' have to shape-up, and drop all those implementation approaches that were valid and comfortable. We don't have any of that nonsense over here! If you want your damned existing code to run fast, well then, by golly you'd better make sure you redesign it too!" ?

... and all because there's no accessible way to inhibit default initialization?  The issues at hand are several:

1) the original implementation was, and still is, a perfectly valid approach (given the requirements). It is also executes rather efficiently. The same pattern is quite likely to occur in original D code also. Let's try to avoid whether other approaches are better or worse; that doesn't help. Not even the best education can thoroughly resolve such problems. For the record, your alternative still needs an additional boundary-check plus error-message for equivalent pathological conditions (out of memory).

2) what you are now suggesting is that the program should be redesigned instead. That is simply not realistic for working, optimal code. The code compiled and executed without too much effort, but it exhibits performance issues. That's what drove the foray into this topic. I will probably fix it with the assembly-code thoughtfully provided by AJ (and thanks to Ben also for both his suggestions) but that's hardly an accessible, or portable, resolution in the general sense.

3) the solution offered (by both yourself and by Ben) is not allocated on the stack. The whole point here is to utilize the stack because it's a much faster means of providing a temporary workspace. Going to the heap means a partial redesign, and the program will still run slower in D than it did originally. Forcing stack arrays to initialize will /always/ be dramatically slower than the equivalent C/C++ code, whereas a simple embellishment to the existing initialization mechanism would resolve that completely; and in a jiffy. This is about choice, Walter, and supporting the programmer in what they are doing.

4) the approach to addressing this seems to be one of "guilty until proven innocent". That is, there doesn't seem to be any notion on your part that this might, actually, be a valid observation. With solid number to back it up. You're basically saying, " ... the approach never had, and never will, have any validity whatsoever. Rip out the code and do it just like I would". I do sincerely hope that I'm misunderstanding you, but that's kinda' how it has been coming across.

May I ask why some easy manual control over default-initialization is such a terrible thing? Is it really /so/ impossible that you'd rather force people into re-implementing and retesting parts of their existing codebase instead (as you suggest above) ?

Or is there perhaps some fundamental ideology at stake, that I just don't see?




"Walter" <newshound@digitalmars.com> wrote in message news:cfgqv4$2lq9$1@digitaldaemon.com...
>
> "van eeshan" <vanee@hotmail.net> wrote in message news:cfge6g$2g1j$1@digitaldaemon.com...
> > Heavy-duty text processing. The coder wasn't being lazy at all, as out-of-bounds conditions are being checked for. The allocated
(temporary)
> > workspace is typically used in only a small amounts, but sporadically
will
> > get used more fully. The approach taken was apparently "we'll check for end-of-buffer, but if anything exceeds these limits, then it's so beyond
> the
> > design-specification that it's an error condition". I understand that to
> be
> > a rather common approach. It's certainly valid, and rather effective.
The
> D
> > approach to this is, " ...you /vill/ pay ze initialization cost,
> regardless
> > of vot ze design!"
>
> Here's an example of an alternate way to do it, for code that would typically use only a small amount, but occaisionally could use a great
deal.
> It can also be set up to never overflow (at least until all memory is exhausted) by repeatedly resizing it. This has the advantage of not
needing
> to set up any error recovery, or create and document an error message for the limits.
>
> import std.stdio;
>
> char[] formatter(char[] s)
> {
>     if (s.length < 14)        // if our passed buffer isn't big enough
>         s.length = 14;        // yes, we can reallocate things that were
> originally on the stack
>     s[0..14] = "abcdefghijklmn";    // copy result into s[]
>     return s;
> }
>
>
> void main()
> {   char[4] workspace;    // assume 4 is size typically needed in
> formatter()
>     char[] s;
>
>     s = formatter(workspace);
>     writefln(s);
> }
>
>
>

Addendum.

I misread your code somewhat, Water, but what you suggest has a fatal flaw in it:  you are still initializing the original stack-based array, and you're making the assumption that the typical size is very small. Further, you are then extending the array via the heap which will, I imagine, initialize the extended part of the array. That just doesn't work because:

a) there's a significant amount of effort to convert all the "workers" to do what you suggest. Plus, the code is less efficient, there's more of it, and there's possible heap-fragmentation involved.

b) the initial size needs to be around the 2 to 3KB mark. Given that, your example is hardly faster than the original code. In fact, the initialization cost is ~57000% slower than the equivalent C/C++ array allocation. That's better than ~88000%, but who's to quibble at these levels?

I wish it were so simple as your suggestion conveyed. Conversely, if there were a syntactic means of optionally inhibiting the array initialization, there would be no related issue at all. We could all be radiantly happy, and have a beer or something.




"Walter" <newshound@digitalmars.com> wrote in message news:cfgqv4$2lq9$1@digitaldaemon.com...
>
> "van eeshan" <vanee@hotmail.net> wrote in message news:cfge6g$2g1j$1@digitaldaemon.com...
> > Heavy-duty text processing. The coder wasn't being lazy at all, as out-of-bounds conditions are being checked for. The allocated
(temporary)
> > workspace is typically used in only a small amounts, but sporadically
will
> > get used more fully. The approach taken was apparently "we'll check for end-of-buffer, but if anything exceeds these limits, then it's so beyond
> the
> > design-specification that it's an error condition". I understand that to
> be
> > a rather common approach. It's certainly valid, and rather effective.
The
> D
> > approach to this is, " ...you /vill/ pay ze initialization cost,
> regardless
> > of vot ze design!"
>
> Here's an example of an alternate way to do it, for code that would typically use only a small amount, but occaisionally could use a great
deal.
> It can also be set up to never overflow (at least until all memory is exhausted) by repeatedly resizing it. This has the advantage of not
needing
> to set up any error recovery, or create and document an error message for the limits.
>
> import std.stdio;
>
> char[] formatter(char[] s)
> {
>     if (s.length < 14)        // if our passed buffer isn't big enough
>         s.length = 14;        // yes, we can reallocate things that were
> originally on the stack
>     s[0..14] = "abcdefghijklmn";    // copy result into s[]
>     return s;
> }
>
>
> void main()
> {   char[4] workspace;    // assume 4 is size typically needed in
> formatter()
>     char[] s;
>
>     s = formatter(workspace);
>     writefln(s);
> }
>
>
>

I've been trying to convert this to a mixin, but not having much luck. Guess I don't know enough about templates ... can you point me in the right direction please Jill? Or will a mixin always place this inside its own private function scope (and thus restore ESP before the array can be used) ?


"Arcane Jill" <Arcane_member@pathlink.com> wrote in message news:cff6a9$1ugb$1@digitaldaemon.com...
> In article <cfete2$1p7g$1@digitaldaemon.com>, van eeshan says...
>
> >Currently, if you want to quickly allocate an array on the stack you must do something like the following:
> >
> >  char[] array = (cast(char *) alloca(Size))[0..Size];
>
> My experiments seem to suggest that the following actually works rather
well.
>
> #    void f()
> #    {
> #        ubyte[] a;
> #        asm
> #        {
> #            sub ESP,1000;    // Reserve 1000 bytes
> #            mov a,1000;      // Set a.length = 1000
> #            mov a+4,ESP;     // Set &a[0] to reserved bytes
> #        }
> #    }
>
>

"van eeshan" <vanee@hotmail.net> wrote in message news:cfh14k$2ouk$1@digitaldaemon.com...
> I misread your code somewhat, Water, but what you suggest has a fatal flaw in it:  you are still initializing the original stack-based array, and you're making the assumption that the typical size is very small.

I'm confused - you wrote: "The allocated (temporary) workspace is typically used in only a small amounts, but sporadically will get used more fully." My suggestion was tuned to that.

> Further,
> you are then extending the array via the heap which will, I imagine,
> initialize the extended part of the array.

That's correct.

> That just doesn't work because:
> a) there's a significant amount of effort to convert all the "workers" to
do
> what you suggest.

Correct, but resizing dynamic arrays in D is pretty easy. It's not as klunky and error-prone as in C.

> Plus, the code is less efficient,

Since the resize will only happen in atypical cases, its efficiency should not impact overall performance.

> there's more of it, and
> there's possible heap-fragmentation involved.

Heap fragmentation is much less of an issue than it used to be, with large memory pools and virtual memory. I know how to build a gc that will compact memory to deal with fragmentation when it does arise, so although this is not in the current D it is not a technical problem to do it.

> b) the initial size needs to be around the 2 to 3KB mark. Given that, your example is hardly faster than the original code. In fact, the
initialization
> cost is ~57000% slower than the equivalent C/C++ array allocation. That's better than ~88000%, but who's to quibble at these levels?

If your app typically is going to fill 2 to 3 Kb, I suggest using malloc()
(or alloca()) for it. The handful of extra instructions to allocate via
malloc as opposed to the stack will be lost in the thousands of instructions
needed to fill 2 to 3 Kb.

> I wish it were so simple as your suggestion conveyed. Conversely, if there were a syntactic means of optionally inhibiting the array initialization, there would be no related issue at all. We could all be radiantly happy,
and
> have a beer or something.

Allocating large, uninitialized arrays on the stack has its own problems:

1) The uninitialized data that is on the stack will get scanned by the garbage collector looking for any references to allocated memory. Since the uninitialized data consists of old D stack frames, it is highly likely that some of that garbage will look like references into the gc heap, and the gc memory will not get freed. This problem really does happen, and can be pretty frustrating to track down. Some of my C code that uses GC gets a memset() on the stack frame for that reason.

2) It's possible for a function to pass out of it a reference to data on that function's stack frame. By then allocating a new stack frame over the old data, and not initializing, the reference to the old data may still appear to be valid. The program will then behave erratically. Initializing all data on the stack frame will greatly increase the probability of forcing that bug into the open in a repeatable manner.

3) Large arrays on the stack bring up the specter of stack exhaustion with even modest amounts of recursion.

That said, there are things I can do to generate faster code for the initialization.

"van eeshan" <vanee@hotmail.net> wrote in message news:cfgvi5$2npu$1@digitaldaemon.com...
> 1) the original implementation was, and still is, a perfectly valid
approach
> (given the requirements).

And it is valid and works in D.

> It is also executes rather efficiently. The same
> pattern is quite likely to occur in original D code also. Let's try to
avoid
> whether other approaches are better or worse; that doesn't help. Not even the best education can thoroughly resolve such problems. For the record, your alternative still needs an additional boundary-check

Yes.

> plus error-message
> for equivalent pathological conditions (out of memory).

This is not necessary, because very few programs can proceed if they run out of memory, so they just issue an error message and abort. In D, this is handled automatically - running out of memory throws an exception with a message in it, if you don't catch the exception, the message is printed and the program aborted. For nearly all programs, this is the right behavior.

> 2) what you are now suggesting is that the program should be redesigned instead. That is simply not realistic for working, optimal code. The code compiled and executed without too much effort, but it exhibits performance issues. That's what drove the foray into this topic. I will probably fix
it
> with the assembly-code thoughtfully provided by AJ (and thanks to Ben also for both his suggestions) but that's hardly an accessible, or portable, resolution in the general sense.

I suggest the alloca() approach, and do some timing tests on the real app with it vs AJ's approach. I'm willing to bet you a beer that you won't be able to measure the difference, especially if the typical use of the array will fill it 2 or 3 Kb worth.

> 3) the solution offered (by both yourself and by Ben) is not allocated on
> the stack.

The alloca() version is.

> The whole point here is to utilize the stack because it's a much
> faster means of providing a temporary workspace. Going to the heap means a
> partial redesign, and the program will still run slower in D than it did
> originally. Forcing stack arrays to initialize will /always/ be
dramatically
> slower than the equivalent C/C++ code, whereas a simple embellishment to
the
> existing initialization mechanism would resolve that completely; and in a jiffy. This is about choice, Walter, and supporting the programmer in what they are doing.
>
> 4) the approach to addressing this seems to be one of "guilty until proven innocent". That is, there doesn't seem to be any notion on your part that this might, actually, be a valid observation. With solid number to back it up. You're basically saying, " ... the approach never had, and never will, have any validity whatsoever. Rip out the code and do it just like I
would".
> I do sincerely hope that I'm misunderstanding you, but that's kinda' how
it
> has been coming across.
>
> May I ask why some easy manual control over default-initialization is such
a
> terrible thing? Is it really /so/ impossible that you'd rather force
people
> into re-implementing and retesting parts of their existing codebase
instead
> (as you suggest above) ?
>
> Or is there perhaps some fundamental ideology at stake, that I just don't see?

Uninitialized data can be a source of bugs and trouble, as I pointed out in my other posting, even when used correctly. One design goal of D is to improve reliability and portability by eliminating sources of undefined behavior, and uninitialized data is one huge source of undefined, unportable, erratic and unpredictable behavior. I'm trying to squeeze that out of the normal constructs in D - but access to C functions and inline assembler is there for folks who really need it.

Give the other methods presented a chance, and time them in context.

In article <cfhhbe$3jf$1@digitaldaemon.com>, Walter says...

>I know how to build a gc that will compact
>memory to deal with fragmentation when it does arise, so although this is
>not in the current D it is not a technical problem to do it.

That's probably good news, but:

Will it be possible to mark specific arrays on the heap as "immovable"? (Please say yes. I'm sure it is not a technical problem).

Arcane Jill