Subject: Re: allocator and GC locality, and locality generally (was Re: cost of malloc)
From: Erik Naggum <>
Date: 1995/08/11
Newsgroups: comp.lang.dylan,comp.lang.misc,comp.lang.lisp,comp.object,comp.arch
Message-ID: <>

[Stefan Monnier]

|   ignoring the fact that looking at the stack is not portable,

memory allocation is never portable.  I just realized that this may be why
C++ is so bad in this area, and why C++ programmers write their own
allocators all the time.  non-portable things should be isolated and have
geniuses optimize the hell out of them.

|   there is another problem: how to you plan on making the thing fast
|   enough ?  (improving locality is good, but you don't want your
|   allocator to take ten times as much time, do you?)

someone said that one page fault costs on the scale of 10,000,000
instructions on today's CPU, memory, and disk speeds.  if you avoid a page
fault, you have time to spare.  later, you can optimize the savings...

here's one statistic: I have helped a math grad student write a C program
that does some horrible analysis on millions of points in fluid mechanics.
she insisted upon an access pattern that trashed the machine she ran it on,
so I wrote a custom matrix allocator that matched her access pattern, and
runtime fell with 70%.  bonus: this allocator is also *much* faster than
your regular 5000 malloc calls to set up the indirection vector into the
matrix, since it allocates all of the memory in one fell swoop.  it could
of course be greatly improved with a language that let me specify how to
access the memory, but worrying about the allocator does pay off at times.

#<Erik 3017137801>
#<Xyzzy 202B370B73>