Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.forth > #10579

Re: Sparse sets

Show all headers | View raw

mhx@iae.nl (Marcel Hendrix) writes:
>I have a hard time believing the quoted advantages of sparse sets myself

The advantages are real.  The problem is that this representation
requires a lot of memory, and actually uses it (so the OS has to clear
it at the start, and it has to be kept in main memory, and it will
affect cache misses), although the memory is only accessed sparsely.

> A common use of these sparse sets is 
> with register allocation algorithms in compilers, which have a 
> fixed universe (the number of registers in the machine) and are
> updated and cleared frequently during a single processing run.

Actually the universe in the register allocation application is the
number of pseudo-registers (aka live ranges) in the function.  The
number of registers in the machine is small, so you don't need a
sparse representation for that.

Anyway, the only use of this representation in register allocation in
know of was the one described in the paper.  Appel and George
represented the conclict graph (which was the main use for this sparse
set representation in the work of Briggs et al.) in a hash table: much
smaller memory, also average constant-time insertion and lookup, and
acceptable clearing time.

Still, I find this set representation instructive, in its advertised
properties, why they are important for some applications, and in the
not so obvious side effects, which make it less of a good idea than
one thinks at first.

- anton
-- 
M. Anton Ertl  http://www.complang.tuwien.ac.at/anton/home.html
comp.lang.forth FAQs: http://www.complang.tuwien.ac.at/forth/faq/toc.html
     New standard: http://www.forth200x.org/forth200x.html
   EuroForth 2011: http://www.euroforth.org/ef11/

Back to comp.lang.forth | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

Sparse sets mhx@iae.nl (Marcel Hendrix) - 2012-03-26 20:49 +0200
  Re: Sparse sets anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2012-03-27 14:43 +0000
  Re: Sparse sets David Kuehling <dvdkhlng@gmx.de> - 2012-03-28 23:41 +0200

csiph-web