Re: Parallelizing (WAS: Death by pointers.)

hbaker@netcom.com (Henry Baker) writes:


> [Arrays have much better cache behavior than linked lists but ...]


> Since you are writing compilers, and compilers are notorious for having
> lots of little tables, each of which puts an arbitrary constraint on the
> language being compiled, aren't you making life difficult for your customers?


!!!!! NO!
I hate idiot limits.
No limits to my arrays.
They resize as required, or get a precomputed size that's "just right".


For the precompute variety: you need some sort of prepass to count how many
you need. Optimizer compilers have too many passes already; throwing a
counter into an eariler one is easy.


For resizing arrays, they double in size as they run out. Requires a quicky
test&increment in the common case, with a doubling realloc log_N times.
Total worst-case data movement is 2N, and slop is O(N/2). You can fiddle
with the worst-case constants by resizing using a constant other than 2.
Data movement is actually fairly cheap, since block copy uses the memory
hierarchy "exactly right". I have a friend (hi Preston!) who believes you
should always precompute, but it's easy to resize and it's never the
bottleneck.




> There has been a lot of work on automatically choosing data structures. I
> seem to recall that Jim Low's thesis in the 1970's was on this subject.


And all the SETL work as well.




> However, instead of building this intelligence into the compiler, it might
> be nice to build this into a 'smart' template capability for C++ (or
> C+++).


Sigh. Templates. Someday Real Soon Now a compiler on my desk will quickly
compile templates into quick code. Meanwhile I avoid 'em. Another evil
"premature optimization" that I'll look back on in 5 years and wonder why
I bothered.


Cliff


P.S. I'd guess I'd settle for a compiler that quickly compiles templates
with debugging turned on into code that doesn't double (or worse!) my
link times.


--
Cliff Click Compiler Researcher & Designer
RISC Software, Motorola PowerPC Compilers
cliffc@risc.sps.mot.com (512) 891-7240
--

Return to the comp.compilers page.
Search the comp.compilers archives again.