🚀 go-pugleaf

In article <9532600.2695@mulga.cs.mu.OZ.AU>,
Fergus Henderson <fjh@munta.cs.mu.OZ.AU> wrote:
>ark@research.att.com (Andrew Koenig) writes:
>
>>ralphs@tesser.com (Ralph Shnelvar) writes:
>>
>>> I haven't even peeked at the STL but am wondering if there is support
>>> for a disk based sorting and/or indexing algorithms.
>>
>>Sure.  All you have to do is write a class that meets the
>>relevant iterator constraints and grants access to your
>>disk file.  Then all the algorithms will work.
>
>That misses the point a bit doesn't it?  To get reasonable efficiency,
>wouldn't you want to use a different algorithm for disk based sorting
>than for in-memory sorting?

Not necessarily.  Given that processor and disk speeds keep getting
further apart, locality of reference is increasingly important
for "in memory" data structures, so the same principles apply to
file sorting as to in-memory sorting.   What really matters is
the size and of the data set and the patterns of access, not whether
it's file data or a heap-allocated data structure.  A sort routine
for a large data structure should have good locality if you want
it to have good and robust performance.  In a virtual memory environment,
you don't want to assume that random access is actually a good idea.

In principle, a p-store should be more efficient than using files,
because you don't have to translate formats to move things into ad
out of virtual memory, and because the operating system doesn't
have to cache recently-transferred stuff in both the file cache
and the virtual memory cache.  After all, it's kinda silly that we
have two parallel memory hierarchies, both consisting of RAM and
disk, and we copy back and forth between them when doing I/O.

This is the motivation behind our work with persistent object stores.
Rather than having to read and write your C++ data structures to
and from files, you get the effect of a virtual memory that lives
forever.  If you want to operate on it, just follow pointers and
page it in automatically.

This means, of course, that data structure designers have to write
good classes for large data structures.  E.g., we've implemented B+
trees as a C++ class, so that you can get the nice locality effects
of B+ trees without having to externalize all of your data and go
through a krufty file interface.  We want to make the B+ trees STL
compatible, so that you can replace another collection implementation
with B+ trees if you decide that's more appropriate, locality-wise.

The nice thing about persistent C++ is that you can plug in different
data structures without worrying so much whether they should be coded
to be stored in files or "in memory".  The same code works for either.

Of course, you *do* have to pay attention to locality.  Getting
rid of the file/memory distinction doesn't make deep problems go
away;  it just makes tedious annoying unnecessary problems go away
by getting rid of the so-called "impedance mismatch" between file
and in-memory data.  

-- 
| Paul R. Wilson, Comp. Sci. Dept., U of Texas @ Austin (wilson@cs.utexas.edu)
| Papers on memory allocators, garbage collection, memory hierarchies,
| persistence and  Scheme interpreters and compilers available via ftp from 
| ftp.cs.utexas.edu, in pub/garbage (or http://www.cs.utexas.edu/users/wilson/)

---
[ comp.std.c++ is moderated.  Submission address: std-c++@ncar.ucar.edu.
  Contact address: std-c++-request@ncar.ucar.edu.  The moderation policy
  is summarized in http://dogbert.lbl.gov/~matt/std-c++/policy.html. ]