Re: GC in Jon's raytracing benchmark


As a little test, I spent last night toying with the C++ implementation of
my ray tracer. This is a good program to use because it has a similar
distribution of 3D vector lifetimes to values in typical FP programs rather
than imperative programs. However, my results weren't all as I'd
expected...

Using new and delete with reference counting, the program slows down by
about an order of magnitude. Some of that slow-down can be attributed to
the overhead of reference counting. So I was right that new and delete are
substantially slower than real GCs.

Jon Harrop wrote:
> The simplest way to address this issue is to switch to C++ and use STL
> containers instead of malloc and free. This is actually likely to make
> your code shorter rather than longer and the STL's built-in allocators are
> likely to outperform malloc and free because they are better optimised for
> this kind of use.

However, this suggestion of mine was grossly off the money. It seems that
improving upon new and delete isn't as easy as I had assumed, particularly
using the STL.

I was quite surprised when replacing my calls to new and delete with
inserting and deleting from an STL list that my program slowed down by an
order of magnitude. Worse, the STL never reclaimed the memory so it ran out
of memory on my usual test.

> The next step would be to write your own allocation and deallocation
> routines on top of malloc and free (or new and delete). I've never done
> this but I'd recommend reading up on GC papers and asking GC experts which
> books they recommend. You can pretty much make this task as difficult as
> you want. I think it would actually be quite fun (it's on my "to do" list)
> because you can measure the distributions of lifetimes and sizes of values
> and play around with multiple allocators or adaptive allocation and so on.

I've had a quick play with writing a custom allocator and deallocator using
the STL and all of my results are much slower than using new and delete.

I tried having young and old generations, measuring the distributions of
object lifetimes in terms of both real-time and references made. I tried
linearly searched STL vectors of objects, keeping a balanced binary tree
(STL set) of free elements, and keeping a stack of free elements. None of
these approaches comes close to the performance of using new and delete.

One question remains though - are new and delete "as good as" malloc and
free? I've yet to try malloc and free but I expect they are exactly the
same...

--
Dr Jon D Harrop, Flying Frog Consultancy
http://www.ffconsultancy.com
.

Relevant Pages

  • Re: realloc equivalent for new
    ... however what are those allocators and unitialised memory facilities about. ... > malloc vs the special realloc implementation). ... > What I referred to above (the vector vs malloc performance issue) was ...
    (comp.lang.cpp)
  • Re: realloc equivalent for new
    ... > however what are those allocators and unitialised memory facilities about. ... if you implememt your own malloc like library. ... >> heaps (the libc malloc vs the special realloc implementation). ... sorting a vectorwould have comparable performance to sorting a ...
    (comp.lang.cpp)
  • Re: Does Bill Gates know about the DDK regarding C++?
    ... I use STL too, with allocators ... STL is a nightmare in terms of memory fragmentation. ... C++ suggests to use exceptions to recover from such situations. ... system-level development. ...
    (microsoft.public.development.device.drivers)
  • Re: Implementing a custom memory allocator
    ... functionnal difference between malloc and HeapAlloc? ... run-time allocators that are used in all other languages as well. ... presented are "custom memory allocators", then my answer to the OP is ...
    (microsoft.public.win32.programmer.kernel)
  • Re: How to choose buffer size?
    ... - Some malloc() implementations use fundamental "block sizes" ... request is very nearly the worst thing you can ask for. ... How many pure buddy system allocators are there? ...
    (comp.lang.c)