Subject: Re: allocator and GC locality, and locality generally (was Re: cost of malloc) From: Erik Naggum <erik@naggum.no> Date: 1995/08/11 Newsgroups: comp.lang.dylan,comp.lang.misc,comp.lang.lisp,comp.object,comp.arch Message-ID: <19950811T135001Z@naggum.no> [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>