[M3devel] M3 programming problem : GC efficiency / per-thread storage areas?

[Tony Hosking]

I have one more question that I forgot to ask before.  Did you  
evaluate performance with -O3 optimization in the backend?

Generally, I have the following in my m3_backend specs so that turning  
on optimization results in -O3 (and lots of lovely inlining):

proc m3_backend (source, object, optimize, debug) is
   local args =
   [
     "-m32",
     "-quiet",
     source,
     "-o",
     object,
     % fPIC really is needed here, despite man gcc saying it is the  
default.
     % This is because man gcc is about Apple's gcc but m3cg is
     % built from FSF source.
     "-fPIC",
     "-fno-reorder-blocks"
   ]
   if optimize  args += "-O3"  end
   if debug     args += "-gstabs"  end
   if M3_PROFILING args += "-p" end
   return try_exec (m3back, args)
end


On 17 Oct 2008, at 09:32, Mika Nystrom wrote:

> Ok I am sorry I am slow to pick up on this.
>
> I take it the problem is actually the Upthread.getspecific routine,
> which itself calls something get_curthread somewhere inside pthreads,
> which in turn involves a context switch to the supervisor---the  
> identity
> of the current thread is just not accessible anywhere in user space.
> Also explains why this program runs faster with my old PM3, which uses
> longjmp threads.
>
> The only way to avoid it (really) is to pass a pointer to the
> Thread.T of the currently executing thread in the activation record
> of *every* procedure, so that allocators can find it when  
> necessary....
> but that is very expensive in terms of stack memory.
>
> Or I can just make a structure like that that I pass around where
> I need it in my own program.  Thread-specific and user-managed.
>
> I believe I have just answered all my own questions, but I hope
> Tony will correct me if my answers are incorrect.
>
>    Mika
>
> Tony Hosking writes:
>> I suspect part of the overhead of allocation in the new code is the
>> need for thread-local allocation buffers, which means we need to
>> access thread-local state.  We really need an efficient way to do
>> that, but pthreads thread-local accesses may be what is killing you.
>>
>> On 17 Oct 2008, at 00:30, Mika Nystrom wrote:
>>
>>> Hi Tony,
>>>
>>> I figured you would chime in!
>>>
>>> Yes, @M3noincremental seems to make things consistently a tad bit
>>> slower (but a very small difference), on both FreeBSD and Linux.
>>> @M3nogc makes a bigger difference, of course.
>>>
>>> Unfortunately I seem to have lost the code that did a lot of memory
>>> allocations.  My tricks (as described in the email---and others!)
>>> have removed most of the troublesome memory allocations, but now
>>> I'm stuck with the mutex instead...
>>>
>>>     Mika
>>>
>>> Tony Hosking writes:
>>>> Have you tried running @M3noincremental?
>>>>
>>>> On 16 Oct 2008, at 23:32, Mika Nystrom wrote:
>>>>
>>>>> Hello Modula-3 people,
>>>>>
>>>>> As I mentioned in an earlier email about printing structures  
>>>>> (thanks
>>>>> Darko), I'm in the midst of coding an interpreter embedded in
>>>>> Modula-3.  It's a Scheme interpreter, loosely based on Peter
>>>>> Norvig's
>>>>> JScheme for Java (well it was at first strongly based, but more  
>>>>> and
>>>>> more loosely, if you know what I mean...)
>>>>>
>>>>> I expected that the performance of the interpreter would be much
>>>>> better in Modula-3 than in Java, and I have been testing on two
>>>>> different systems.  One is my ancient FreeBSD-4.11 with an old  
>>>>> PM3,
>>>>> and the other is CM3 on a recent Debian system.  What I am finding
>>>>> is that it is indeed much faster than JScheme on FreeBSD/PM3
>>>>> (getting
>>>>> close to ten times as fast on some tasks at this point), but on
>>>>> Linux/CM3 it is much closer in speed to JScheme than I would like.
>>>>>
>>>>> When I started, with code that was essentially equivalent to
>>>>> JScheme,
>>>>> I found that it was a bit slower than JScheme on Linux/CM3 and
>>>>> possibly 2x as fast on FreeBSD/PM3.  On Linux/CM3, it appears to
>>>>> spend most of its time in (surprise, surprise!) memory allocation
>>>>> and garbage collection.  The speedup I have achieved between the
>>>>> first implementation and now was due to the use of Modula-3
>>>>> constructs
>>>>> that are superior to Java's, such as the use of arrays of RECORDs
>>>>> to make small stacks rather than linked lists.  (I get readable
>>>>> code with much fewer memory allocations and GC work.)
>>>>>
>>>>> Now, since this is an interpreter, I as the implementer have  
>>>>> limited
>>>>> control over how much memory is allocated and freed, and where  
>>>>> it is
>>>>> needed.  However, I can sometimes fall back on C-style memory
>>>>> management,
>>>>> but I would like to do it in a safe way.  For instance, I have
>>>>> special-cased
>>>>> evaluation of Scheme primitives, as follows.
>>>>>
>>>>> Under the "normal" implementation, a list of things to evaluate is
>>>>> built up, passed to an evaluation function, and then the GC is  
>>>>> left
>>>>> to sweep up the mess.  The problem is that there are various  
>>>>> tricky
>>>> routes by which references can escape the evaluator, so you can't
>>>>> just assume that what you put in is going to be dead right after
>>>>> an eval and free it.  Instead, I set a flag in the evaluator,  
>>>>> which
>>>>> is TRUE if it is OK to free the list after the eval and FALSE if
>>>>> it's unclear (in which case the problem is left up to the GC).
>>>>>
>>>>> For the vast majority of Scheme primitives, one can indeed free  
>>>>> the
>>>>> list right after the eval.  Now of course I am not interested
>>>>> in unsafe code, so what I do is this:
>>>>>
>>>>> TYPE Pair = OBJECT first, rest : REFANY; END;
>>>>>
>>>>> VAR
>>>>> mu := NEW(MUTEX);
>>>>> free : Pair := NIL;
>>>>>
>>>>> PROCEDURE GetPair() : Pair =
>>>>> BEGIN
>>>>>  LOCK mu DO
>>>>>    IF free # NIL THEN
>>>>>      TRY
>>>>>        RETURN free
>>>>>      FINALLY
>>>>>        free := free.rest
>>>>>      END
>>>>>    END
>>>>>  END;
>>>>>  RETURN NEW(Pair)
>>>>> END GetPair;
>>>>>
>>>>> PROCEDURE ReturnPair(cons : Pair) =
>>>>> BEGIN
>>>>>  cons.first := NIL;
>>>>>  LOCK mu DO
>>>>>    cons.rest := free;
>>>>>    free := cons
>>>>>  END
>>>>> END ReturnPair;
>>>>>
>>>>> my eval code looks like
>>>>>
>>>>> VAR okToFree : BOOLEAN; BEGIN
>>>>>
>>>>> args := GetPair(); ...
>>>>> result := EvalPrimitive(args, (*VAR OUT*) okToFree);
>>>>>
>>>>> IF okToFree THEN ReturnPair(args) END;
>>>>> RETURN result
>>>>> END
>>>>>
>>>>> and this does work well.  In fact it speeds up the Linux
>>>>> implementation
>>>>> by almost 100% to recycle the lists like this *just* for the
>>>>> evaluation of Scheme primitives.
>>>>>
>>>>> But it's still ugly, isn't it?  There's a mutex, and a global
>>>>> variable.  And yes, the time spent messing with the mutex is
>>>>> noticeable, and I haven't even made the code multi-threaded yet
>>>>> (and that is coming!)
>>>>>
>>>>> So I'm thinking, what I really want is a structure that is  
>>>>> attached
>>>>> to my current Thread.T.  I want to be able to access just a single
>>>>> pointer (like the free list) but be sure it is unique to my  
>>>>> current
>>>>> thread.  No locking would be necessary if I could do this.
>>>>>
>>>>> Does anyone have an elegant solution that does something like  
>>>>> this?
>>>>> Thread-specific "static" variables?  Just one REFANY would be  
>>>>> enough
>>>>> for a lot of uses...  seems to me this should be a frequently
>>>>> occurring problem?
>>>>>
>>>>>   Best regards,
>>>>>     Mika
>>>>>
>>>>>
>>>>>
>>>>>
>>>>>
>>>>>