January 12, 2009
Brad Roberts wrote:
> Andrei Alexandrescu wrote:
>> Weed wrote:
>>> Weed пишет:
>>>
>>>>>> 4. Java and C# also uses objects by reference? But both these of
>>>>>> language are interpreted. I assume that the interpreter generally with
>>>>>> identical speed allocates memory in a heap and in a stack, therefore
>>>>>> authors of these languages and used reference model.
>>>>>>
>>>>> Neither of these languages are interpreted, they both are compiled into
>>>>> native code at runtime.
>>>> Oh!:) but I suspect such classes scheme somehow correspond with
>>>> JIT-compilation.
>>>>
>>> I guess allocation in Java occurs fast because of usage of the its own
>>> memory manager.
>>>     I do not know how it is fair, but:
>>> http://www.ibm.com/developerworks/java/library/j-jtp09275.html
>>>
>>> "Pop quiz: Which language boasts faster raw allocation performance, the
>>> Java language, or C/C++? The answer may surprise you -- allocation in
>>> modern JVMs is far faster than the best performing malloc
>>> implementations. The common code path for new Object() in HotSpot 1.4.2
>>> and later is approximately 10 machine instructions (data provided by
>>> Sun; see Resources), whereas the best performing malloc implementations
>>> in C require on average between 60 and 100 instructions per call
>>> (Detlefs, et. al.; see Resources)."
>> Meh, that should be taken with a grain of salt. An allocator that only
>> bumps a pointer will simply eat more memory and be less cache-friendly.
>> Many applications aren't that thrilled with the costs of such a model.
>>
>> Andrei
> 
> Take it as nicely seasoned.  The current jvm gc and memory subsystem is
> _extremely_ clever.  However, it completely relies on the ability to
> move objects during garbage collection.  If it was purely the allocator
> that behaved that way, you'd be right.  But it's interaction with the gc
> is where the system comes together to form a useful whole.

I understand. My point is that a 10-cycles-per-allocation allocator will necessarily use more memory than one that attempts to reuse memory. There's no way around that. I mean we know what those cycles do :o). Some application don't work well with that. Escape analysis does reduce the number of cache-unfriendly patterns, but, as of today, not to the point the issue can be safely ignored.

There's no contention that GC has made great progress lately, and that's a great thing.


Andrei
January 12, 2009
Weed wrote:
> Bill Baxter пишет:
> 
>>> Please, state critical remarks
>> Your English is really hard to make sense of.
>> That's my guess for why there are no responses.
>> Heck, I'd *like* to respond, but I just can't tell what you're trying to say.
> 
> All is absolutely poor? If not everything, can you select that demands the explanation?

Translation: Is it all bad? Otherwise, can you say what you want clarified?
January 13, 2009
Andrei Alexandrescu пишет:
> Brad Roberts wrote:
>> Andrei Alexandrescu wrote:
>>> Weed wrote:
>>>> Weed пишет:
>>>>
>>>>>>> 4. Java and C# also uses objects by reference? But both these of
>>>>>>> language are interpreted. I assume that the interpreter generally
>>>>>>> with
>>>>>>> identical speed allocates memory in a heap and in a stack, therefore
>>>>>>> authors of these languages and used reference model.
>>>>>>>
>>>>>> Neither of these languages are interpreted, they both are compiled
>>>>>> into
>>>>>> native code at runtime.
>>>>> Oh!:) but I suspect such classes scheme somehow correspond with JIT-compilation.
>>>>>
>>>> I guess allocation in Java occurs fast because of usage of the its own
>>>> memory manager.
>>>>     I do not know how it is fair, but:
>>>> http://www.ibm.com/developerworks/java/library/j-jtp09275.html
>>>>
>>>> "Pop quiz: Which language boasts faster raw allocation performance, the Java language, or C/C++? The answer may surprise you -- allocation in modern JVMs is far faster than the best performing malloc implementations. The common code path for new Object() in HotSpot 1.4.2 and later is approximately 10 machine instructions (data provided by Sun; see Resources), whereas the best performing malloc implementations in C require on average between 60 and 100 instructions per call (Detlefs, et. al.; see Resources)."
>>> Meh, that should be taken with a grain of salt. An allocator that only bumps a pointer will simply eat more memory and be less cache-friendly. Many applications aren't that thrilled with the costs of such a model.
>>>
>>> Andrei
>>
>> Take it as nicely seasoned.  The current jvm gc and memory subsystem is _extremely_ clever.  However, it completely relies on the ability to move objects during garbage collection.  If it was purely the allocator that behaved that way, you'd be right.  But it's interaction with the gc is where the system comes together to form a useful whole.
> 
> I understand. My point is that a 10-cycles-per-allocation allocator

10 *cycles* per allocation?

> will
> necessarily use more memory than one that attempts to reuse memory.
> There's no way around that. I mean we know what those cycles do :o).
> Some application don't work well with that. Escape analysis does reduce
> the number of cache-unfriendly patterns, but, as of today, not to the
> point the issue can be safely ignored.
> 
> There's no contention that GC has made great progress lately, and that's a great thing.

In any case, we cannot add such memory manager in D. And such resource allocation does not approach us, and mandatory creation of objects in a heap does not approach for D.
January 13, 2009
2009/1/13 Weed <resume755@mail.ru>:
> Andrei Alexandrescu пишет:
>> Brad Roberts wrote:
>>> Andrei Alexandrescu wrote:
>>>> Weed wrote:
>>>>> Weed пишет:
>>>>>
>>>>>>>> 4. Java and C# also uses objects by reference? But both these of
>>>>>>>> language are interpreted. I assume that the interpreter generally
>>>>>>>> with
>>>>>>>> identical speed allocates memory in a heap and in a stack, therefore
>>>>>>>> authors of these languages and used reference model.
>>>>>>>>
>>>>>>> Neither of these languages are interpreted, they both are compiled
>>>>>>> into
>>>>>>> native code at runtime.
>>>>>> Oh!:) but I suspect such classes scheme somehow correspond with JIT-compilation.
>>>>>>
>>>>> I guess allocation in Java occurs fast because of usage of the its own
>>>>> memory manager.
>>>>>     I do not know how it is fair, but:
>>>>> http://www.ibm.com/developerworks/java/library/j-jtp09275.html
>>>>>
>>>>> "Pop quiz: Which language boasts faster raw allocation performance, the Java language, or C/C++? The answer may surprise you -- allocation in modern JVMs is far faster than the best performing malloc implementations. The common code path for new Object() in HotSpot 1.4.2 and later is approximately 10 machine instructions (data provided by Sun; see Resources), whereas the best performing malloc implementations in C require on average between 60 and 100 instructions per call (Detlefs, et. al.; see Resources)."
>>>> Meh, that should be taken with a grain of salt. An allocator that only bumps a pointer will simply eat more memory and be less cache-friendly. Many applications aren't that thrilled with the costs of such a model.
>>>>
>>>> Andrei
>>>
>>> Take it as nicely seasoned.  The current jvm gc and memory subsystem is _extremely_ clever.  However, it completely relies on the ability to move objects during garbage collection.  If it was purely the allocator that behaved that way, you'd be right.  But it's interaction with the gc is where the system comes together to form a useful whole.
>>
>> I understand. My point is that a 10-cycles-per-allocation allocator
>
> 10 *cycles* per allocation?
>
>> will
>> necessarily use more memory than one that attempts to reuse memory.
>> There's no way around that. I mean we know what those cycles do :o).
>> Some application don't work well with that. Escape analysis does reduce
>> the number of cache-unfriendly patterns, but, as of today, not to the
>> point the issue can be safely ignored.
>>
>> There's no contention that GC has made great progress lately, and that's a great thing.
>
> In any case, we cannot add such memory manager in D. And such resource allocation does not approach us, and mandatory creation of objects in a heap does not approach for D.

I'm not and expert in garbage collection but...
An interesting point was made yesterday on the GDAlgorithms mailing
list.  Acording to this one game industry veteran, you don't need a
fully moving garbage collector to get many of the benefits.  If *some*
of the memory can be moved around then often that's enough to fill in
the gaps and keep fragmentation down.

So it may be worth while to have a special kind construct for
containing data that the compiler is free to move around.  This type
would have a hidden pointer inside of it that can be moved around by
the gc, but applications would not be allowed to access that pointer.
 And I suppose that means all access to the data would given via
lvalue only.   Probably wouldn't take much on the part of the GC to
provide the necessary hooks.  Just some sort of "relocatable alloc"
call.  Rest could probably be handled in higher level libs.

But like I said I don't know much about GC.

--bb
January 13, 2009
Bill Baxter wrote:
> So it may be worth while to have a special kind construct for
> containing data that the compiler is free to move around.  This type
> would have a hidden pointer inside of it that can be moved around by
> the gc, but applications would not be allowed to access that pointer.
>  And I suppose that means all access to the data would given via
> lvalue only.   Probably wouldn't take much on the part of the GC to
> provide the necessary hooks.  Just some sort of "relocatable alloc"
> call.  Rest could probably be handled in higher level libs.

Interesting. (Link?) Structs in D are supposed to be location transparent (it is unclear to me to what extent this should be enforced vs. just assumed), so if the compiler can show the address of a struct is not taken, it should be free to move it around.

Andrei
January 13, 2009
On Tue, 13 Jan 2009 04:17:22 +0300, Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> wrote:

> Bill Baxter wrote:
>> So it may be worth while to have a special kind construct for
>> containing data that the compiler is free to move around.  This type
>> would have a hidden pointer inside of it that can be moved around by
>> the gc, but applications would not be allowed to access that pointer.
>>  And I suppose that means all access to the data would given via
>> lvalue only.   Probably wouldn't take much on the part of the GC to
>> provide the necessary hooks.  Just some sort of "relocatable alloc"
>> call.  Rest could probably be handled in higher level libs.
>
> Interesting. (Link?) Structs in D are supposed to be location transparent (it is unclear to me to what extent this should be enforced vs. just assumed), so if the compiler can show the address of a struct is not taken, it should be free to move it around.
>
> Andrei

If the compiler can show the address of a struct is not taken, it should recycle the memory :p

January 13, 2009
On Tue, Jan 13, 2009 at 10:17 AM, Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> wrote:
> Bill Baxter wrote:
>>
>> So it may be worth while to have a special kind construct for
>> containing data that the compiler is free to move around.  This type
>> would have a hidden pointer inside of it that can be moved around by
>> the gc, but applications would not be allowed to access that pointer.
>>  And I suppose that means all access to the data would given via
>> lvalue only.   Probably wouldn't take much on the part of the GC to
>> provide the necessary hooks.  Just some sort of "relocatable alloc"
>> call.  Rest could probably be handled in higher level libs.
>
> Interesting. (Link?) Structs in D are supposed to be location transparent (it is unclear to me to what extent this should be enforced vs. just assumed), so if the compiler can show the address of a struct is not taken, it should be free to move it around.

The message doesn't appear to have come up on the list archive yet, but here's the full text:


"""
> Third solution that was popular is to make your data completely
relocatable and allow the blocks to be moved around as needed.

One nice thing I've found is that only some of your data needs to be like this to get the full benefit, because it can move around to fill in the gaps left by all the other fixed-position parts. Especially helpful on consoles, where most of your data is stuff like sound, texture and geometry buffers, which are all trivially relocatable.

TomF.
"""
(TomF is Tom Forsyth, been in the game biz for a long time, now at
Intel working on Larabee)

--bb
January 13, 2009
On Tue, 13 Jan 2009, Bill Baxter wrote:

> I'm not and expert in garbage collection but...
> An interesting point was made yesterday on the GDAlgorithms mailing
> list.  Acording to this one game industry veteran, you don't need a
> fully moving garbage collector to get many of the benefits.  If *some*
> of the memory can be moved around then often that's enough to fill in
> the gaps and keep fragmentation down.
> 
> So it may be worth while to have a special kind construct for
> containing data that the compiler is free to move around.  This type
> would have a hidden pointer inside of it that can be moved around by
> the gc, but applications would not be allowed to access that pointer.
>  And I suppose that means all access to the data would given via
> lvalue only.   Probably wouldn't take much on the part of the GC to
> provide the necessary hooks.  Just some sort of "relocatable alloc"
> call.  Rest could probably be handled in higher level libs.
> 
> But like I said I don't know much about GC.
> 
> --bb

And wouldn't ya know it.. I spent parts of saturday pondering on exactly how to implement exactly that.  I've got most of the code pictured in my head, but none of it written. :)

Maybe one day I'll make the time to try it.

Later,
Brad
January 13, 2009
Hello Bill,

> 2009/1/13 Weed <resume755@mail.ru>:
> 
>> Andrei Alexandrescu пишет:
>> 
>>> Brad Roberts wrote:
>>> 
>>>> Andrei Alexandrescu wrote:
>>>> 
>>>>> Weed wrote:
>>>>> 
>>>>>> Weed пишет:
>>>>>> 
>>>>>>>>> 4. Java and C# also uses objects by reference? But both these
>>>>>>>>> of
>>>>>>>>> language are interpreted. I assume that the interpreter
>>>>>>>>> generally
>>>>>>>>> with
>>>>>>>>> identical speed allocates memory in a heap and in a stack,
>>>>>>>>> therefore
>>>>>>>>> authors of these languages and used reference model.
>>>>>>>> Neither of these languages are interpreted, they both are
>>>>>>>> compiled
>>>>>>>> into
>>>>>>>> native code at runtime.
>>>>>>> Oh!:) but I suspect such classes scheme somehow correspond with
>>>>>>> JIT-compilation.
>>>>>>> 
>>>>>> I guess allocation in Java occurs fast because of usage of the
>>>>>> its own
>>>>>> memory manager.
>>>>>> I do not know how it is fair, but:
>>>>>> http://www.ibm.com/developerworks/java/library/j-jtp09275.html
>>>>>> "Pop quiz: Which language boasts faster raw allocation
>>>>>> performance, the Java language, or C/C++? The answer may surprise
>>>>>> you -- allocation in modern JVMs is far faster than the best
>>>>>> performing malloc implementations. The common code path for new
>>>>>> Object() in HotSpot 1.4.2 and later is approximately 10 machine
>>>>>> instructions (data provided by Sun; see Resources), whereas the
>>>>>> best performing malloc implementations in C require on average
>>>>>> between 60 and 100 instructions per call (Detlefs, et. al.; see
>>>>>> Resources)."
>>>>>> 
>>>>> Meh, that should be taken with a grain of salt. An allocator that
>>>>> only bumps a pointer will simply eat more memory and be less
>>>>> cache-friendly. Many applications aren't that thrilled with the
>>>>> costs of such a model.
>>>>> 
>>>>> Andrei
>>>>> 
>>>> Take it as nicely seasoned.  The current jvm gc and memory
>>>> subsystem is _extremely_ clever.  However, it completely relies on
>>>> the ability to move objects during garbage collection.  If it was
>>>> purely the allocator that behaved that way, you'd be right.  But
>>>> it's interaction with the gc is where the system comes together to
>>>> form a useful whole.
>>>> 
>>> I understand. My point is that a 10-cycles-per-allocation allocator
>>> 
>> 10 *cycles* per allocation?
>> 
>>> will
>>> necessarily use more memory than one that attempts to reuse memory.
>>> There's no way around that. I mean we know what those cycles do :o).
>>> Some application don't work well with that. Escape analysis does
>>> reduce
>>> the number of cache-unfriendly patterns, but, as of today, not to
>>> the
>>> point the issue can be safely ignored.
>>> There's no contention that GC has made great progress lately, and
>>> that's a great thing.
>>> 
>> In any case, we cannot add such memory manager in D. And such
>> resource allocation does not approach us, and mandatory creation of
>> objects in a heap does not approach for D.
>> 
> I'm not and expert in garbage collection but...
> An interesting point was made yesterday on the GDAlgorithms mailing
> list.  Acording to this one game industry veteran, you don't need a
> fully moving garbage collector to get many of the benefits.  If *some*
> of the memory can be moved around then often that's enough to fill in
> the gaps and keep fragmentation down.
> So it may be worth while to have a special kind construct for
> containing data that the compiler is free to move around.  This type
> would have a hidden pointer inside of it that can be moved around by
> the gc, but applications would not be allowed to access that pointer.
> And I suppose that means all access to the data would given via
> lvalue only.   Probably wouldn't take much on the part of the GC to
> provide the necessary hooks.  Just some sort of "relocatable alloc"
> call.  Rest could probably be handled in higher level libs.
> 
> But like I said I don't know much about GC.
> 
> --bb
> 


Recently, I started looking into garbage collection theory.  Of course, the first source I went to was Hans Boem's.  Here's a couple of links that might be interesting:

http://www.hpl.hp.com/personal/Hans_Boehm/gc/complexity.html
http://www.hpl.hp.com/personal/Hans_Boehm/gc/conservative.html

And a whole list of other articles here:

http://www.hpl.hp.com/personal/Hans_Boehm/gc/

Lots of interesting material... and a fair bit of it is over my head. But, nonetheless, the fundamentals are there.  I'm not sure if some of there studies are accurate, biased, or out-dated since I don't keep up with state-of-the-art gc research.  But, it seems to me, that Hans is still one of the top experts in the field, so some of what's there must be very pertinant.

-JJR


January 13, 2009
Andrei Alexandrescu wrote:
> Weed wrote:
>> Weed пишет:
>>
>>>>> 4. Java and C# also uses objects by reference? But both these of
>>>>> language are interpreted. I assume that the interpreter generally with
>>>>> identical speed allocates memory in a heap and in a stack, therefore
>>>>> authors of these languages and used reference model.
>>>>>
>>>> Neither of these languages are interpreted, they both are compiled into
>>>> native code at runtime.
>>> Oh!:) but I suspect such classes scheme somehow correspond with
>>> JIT-compilation.
>>>
>>
>> I guess allocation in Java occurs fast because of usage of the its own
>> memory manager.
>>     I do not know how it is fair, but:
>> http://www.ibm.com/developerworks/java/library/j-jtp09275.html
>>
>> "Pop quiz: Which language boasts faster raw allocation performance, the
>> Java language, or C/C++? The answer may surprise you -- allocation in
>> modern JVMs is far faster than the best performing malloc
>> implementations. The common code path for new Object() in HotSpot 1.4.2
>> and later is approximately 10 machine instructions (data provided by
>> Sun; see Resources), whereas the best performing malloc implementations
>> in C require on average between 60 and 100 instructions per call
>> (Detlefs, et. al.; see Resources)."
> 
> Meh, that should be taken with a grain of salt. An allocator that only bumps a pointer will simply eat more memory and be less cache-friendly. Many applications aren't that thrilled with the costs of such a model.
> 
> Andrei

Actually, memory allocated in the JVM is very cache-friendly, since two subsequent allocations will always be adjacent to one another in physical memory. And, since the JVM uses a moving GC, long-lived objects move closer and closer together.

Of course, Java programmers tend to be less careful about memory allocation, so they usually consume **way** too much memory and lose the benefits of the moving GC.

Java-the-langauge and Java-the-platform are very efficient, even if the java frameworks and java patterns tend to bloated and nasty.

--benji