The Short Tourist's Guide to Memory Allocaters

There's ancient malloc().

And then there is glibc's malloc():

 (illustration not to scale)

General:

A very good place to start is Mr. Golick's intro: Memory Allocators 101, then there is Mr. Luu's C tutorial, or even Doug Lea's dlmalloc.  But, that's only the beginning of a very good, very long story.

Strategies (the very meat of this post):

There is an interesting survey on the different ways of writing a memory allocator, it's very informative (and well-written),  and useful to know in general (even though it's a little old).

More Specific:

For even more pleasing (and productive) confusion, there's TCMalloc, Lockless and a short paper that compares glibc to the former and the latter.

Also notable is jemalloc, and they have a nice video too.  Here's a neat synopsis of this toy.

Profiling:

TCMalloc has profiling inbuilt (via perftools), Lockless has some hooks and jemalloc has a heap profiler.  If you want to check what glibc malloc gets up to, there's malloc_count, or, you can knit your own, using malloc hooks and struct mallinfo.

The Lockless site has some neat info on how to profile without a profiler, using gcc. (their article collection is also quite a good read [with a very special recommendation for the rather nifty 'Obfuscated Rogue' proggy <3 !]).

Happy alloc()-ing!

Ps.: Stuff I idly wonder about:

None of the above seem to take performance profiles of stuff as they run and then automate the conclusions.

There is probably a very good reason for it (there always is :-) --- but, I wonder what would happen if we had a wrapper that that 'kept score' and did test runs on the inputs it knows about and then swaps in different memory allocators on the next run, depending on what profiles match that particular usage pattern the best.

In other news, here's my sure-fire way of how to beat the backgammon world champion:   you roll a double-6 to run home, and with the final checker, you put their 15th checker on the bar.  EASY! ;-)

+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+

Obligatory New Years' Eve video... Ms Sophie is celebrating her birthday party.  The only problem is that all her guests deceased 25 years ago, and so, the butler has to stand in... (scroll forward to 2:24 to start the actual sketch, but, in full length with the German intro, it still makes a nice ambience, even if you do not speak German ;-)  the rest is, as they say, without words!

Happy New year everyone!!!

Sometimes, that which beeps is gold

I was rooting around the web, trying to find a way of emitting a simple beep for a javascript toy I'm working on and happened upon this piece of code gold.  Nifty!

Promptly I was reminded of this song (oh noes!)

That little Casio the band uses was something else!

Ruby Koans Meditation

Even if you never ever plan to code in Ruby, do check out the Neo Ruby Koans meditation.

It is the cutest, most fun programming course I've ever took.

But be sure to study the Tao of Programming first.

Thus spake the novice programmer:

``It is time for me to begin.''

If at first you don't succeed...

I tidied up the "comments" which are actually defines (what was I thinking?) in this file because, well, they looked messy :)

However, in this case, the position of the defines actually reflected the structure of the data -- something I have never seen before, but it's indeed very handy, once you know what you're looking at.

So, the patch then morphed from 'fixing' what was not broken to adding information about what is going on :)

Since we didn't want Doxygen to pick up that comment since it's only useful when you view the code, I used a /* plain comment */ here.

Outlambda'd !

So, I decide to mail a MUD friend with my OPW success to brag a little about my 'Supersize Me' coding experiment and he shows me his 'Superconcise Me' project!

 *DRUMROLL*

John Tromp scooped "Most Functional" in the 2012 International Obfuscated C contest!

       Int L[A],m,b,*D=A,
        *c,*a=L,C,*U=L,u;s
         (_){u--&&s(a=*a);}
          char*B,I,O;S(){b=b
           --?b:m|read(0,&I,1
            )-1;return~I>>b&1;
             }k(l,u){for(;l<=u;
              U-L<A?*U++=46^l++[
               "-,&,,/.--/,:-,'/"
               ".-,-,,/.-,*,//..,"
              ]:exit(5));}p(Int*m){
             return!*U?*m=S()?U++,!S
            ()?m[1]=p(++U),2:3:1,p(U)
           :S()?U+=2:p(U[1]++),U-m;}x(
          c){k(7*!b,9);*U++=b&&S();c&&x
         (b);}d(Int*l){--l[1]||d(l[d(*l),
        *l=B,B=l,2]);}main(e){for(k(10,33
       ),a[4]-=m=e-2&7,a[23]=p(U),b=0;;e-2
      ?e?e-3?s(D=a),C=a  [3],++1[a=a[2]],d(
     D):c?D=c,c=*D,*D=    a,a=D:exit(L[C+1])
    :C--<23?C=u+m&1?O      =O+O|C&1,9:write(m
   ||(O=C+28),&O,1)+        1:(S(),x(0<b++?k(0,
  6),U[-5]=96:0)):(          D=B?B:calloc(4,X))
 ?B=*D,*D=c,c=D,D[            2]=a,a[++D[1]]++,D
[3]=++C+u:exit(6)              )e=L[C++],u=L[C];}

I don't know the name of the program(this is the obfuscated C contest after all...), but I think it's the Lambda beast.  

And suddenly the Subversion octopus does not look quite as scary anymore, relatively speaking (however, no easier at all!)  If the 'Lamda beast' was a song, I think it would sound like this:

Gratz John, and thank you for a lovely coding perl!