[M3devel] heap vs. stack? (sort of)

[Tony Hosking]

I should say CM3 here.

On Jan 28, 2008, at 11:43 AM, Tony Hosking wrote:

> Modula-3 heap allocation is just bumping a pointer.  The M3 GC is a  
> copying (ie, compacting) collector.  Fast path allocation doesn't  
> even need synchronization since every thread allocates from its own  
> private heap buffer.
>
> On Jan 28, 2008, at 9:00 AM, Jay wrote:
>
>> Both.
>> In thinking about how to write the code, there is no point in  
>> splitting the code into two functions.
>> They are each small and the one is only called once.
>> The language should in general not force me to write functions  
>> merely to work over the type system.
>> <*inline*> is not implemented by the integrated backend. I assume  
>> every function call I write will not be inlined.
>>
>> > Functions can return pointers to open arrays - isn't this enough?
>>
>> Yes that might help.
>> I had tried like
>>
>> PROCEDURE PickBuffer(VAR buf: ARRAY OF CHAR; len: INTEGER): ARRAY  
>> OF CHAR =
>> BEGIN
>>   IF len <= NUMBER(buf)
>>     RETURN buf;
>>   END;
>>   RETURN NEW ARRAY OF CHAR (len);
>> END PickBuffer;
>>
>> PROCEDURE Parse(...)
>> VAR
>>    stack: ARRAY [0..255] OF CHAR;
>>  BEGIN
>>   ...
>>   WITH buf = PickBuffer(stack, len) DO
>>      use buf
>>    END;
>>  END Parse
>>
>> but I couldn't come up with a PickBuffer that the compiler liked.
>>
>> PickBuffer is still a bit iffy.
>>
>> More generally in C++ I would implement that as a template class  
>> where one of the parameters is how much to preallocate. In C I  
>> would implement it as a struct and some functions and the  
>> initialization function would take the preallocated buffer and size.
>>
>> Surely Modula-3 can do either/both of those patterns well and it  
>> doesn't have to be reimplemented over and over.
>>
>> The Modula-3 code I see around the system is way more low level  
>> and repetitive than seems appropriate, more so than C code that I  
>> write.
>>
>> Another example is that it definitely appears that if I try to  
>> compile code with a path like
>> \a\b\c\d\e\f\g\h\a\b\c\d\e\f\g...\foo.m3
>>
>> that has more than around 32 path separators, I'll just get some  
>> random failures since the code just "gives up".
>> M3Path has an array of 32 to store the positions of path separators.
>> That whole chunk of code, to remove \.\ I'll probably rewrite to  
>> be both more efficient and have no such capacity limits.
>> For \.\ it is trivial.
>> For \..\ it takes a bit of cleverness -- rather than rely on any  
>> indefinite amount of storage, what you can do is first reverse the  
>> string, then whenever you se .., bump up a counter, whenever you  
>> see not .., bump it down, only copy from source to dest when the  
>> counter is zero. Roughly.
>>
>> Of course...maybe better here...count the slashes, if there are  
>> more than ~30, do the heap alloc, as in the previous pattern.  
>> Though it'd be nice, since it is possible, to handle arbitrarily  
>> long paths without the heap alloc.
>>
>> In a compacting garbage collection system, heap alloc can be  
>> roughly the cost of incrementing an integer.
>> I do not assume Modula-3 has that, though maybe, and I do not  
>> assume it has particularly fast heap allocation.
>> I have seen heap allocation just be very slow in general and I  
>> avoid it whenever possible/easy/correct.
>>
>> There are competing desires here of course.
>>   1 Be fast.
>>   2 Don't have fixed sized limits. (and esp. don't crash when you  
>> go past them! as I complained about recently..)
>>   3 Don't use "too much" stack, however much that is.
>>
>> The easiest way to do #2 and #3 is always heap alloc exactly how  
>> much you need, but that kills #1.
>>
>>  - Jay
>>
>>
>>
>> > Date: Mon, 28 Jan 2008 14:38:37 +0100
>> > From: lemming at henning-thielemann.de
>> > Subject: RE: [M3devel] heap vs. stack? (sort of)
>> > To: jayk123 at hotmail.com
>> > CC: m3devel at elegosoft.com
>> >
>> >
>> > On Mon, 28 Jan 2008, Jay wrote:
>> >
>> > > I totally want common code, there's just no point in moving it  
>> into a separate function.
>> >
>> > Are you concerned about efficiency or about readability? In the  
>> first case
>> > maybe <* INLINE *> helps?
>> >
>> > > I also tried WITH that got its value from "PickBuffer", also a  
>> useless
>> > > function but at least small, but functions can't return open  
>> arrays.
>> >
>> > Functions can return pointers to open arrays - isn't this enough?
>>
>>
>> Connect and share in new ways with Windows Live. Get it now!