maps to hold ultra large data sets using customer allocators to allocate disk space rather than main memory

[CMOS]

one of the projects im working in currently requires use of ultra
large sized maps, lists, vector, etc. (basically stl containers).
Sizes might grow up to 1000 Million entries. since it is impossible to
have all this data in memory, im planning to implement these
containers to hold data both in memory and disk at the same time.
im not sure this can be achieved using customer allocators and im
wondering if there are any such implementations .

thank you

[James Kanze]

On May 15, 8:42 am, Ian Collins <[e-mail] mwrote:

CMOS wrote:

one of the projects im working in currently requires use of ultra
large sized maps, lists, vector, etc. (basically stl containers).
Sizes might grow up to 1000 Million entries. since it is impossible to
have all this data in memory, im planning to implement these
containers to hold data both in memory and disk at the same time.
im not sure this can be achieved using customer allocators and im
wondering if there are any such implementations .

The short answer is yes, but are you sure you want to?

Are you sure? It's probably possible to do something so that
parts of the map are loaded lazily, but functions like
map<>::operator[] and map<>::iterator ::operator* return
references that are required to be real references, and are
guaranteed to be valid as long as the corresponding entry has
not been erased. I think that that more or less pins any
accessed entry in memory, at its original address. Which means
that while you can load lazily (maybe), you cannot drop an entry
from memory once it has been accessed.

One solution that probably is possible, however, is to put the
map in shared memory, backed by a file, using mmap (or its
Windows equivalent). In theory, I think it is possible to even
allow loading it at an arbitrary address; in practice, the one
time I played this game, we loaded at a fixed adress, and left
the pointer type a T*. We also designed the data structures so
that they only contained PODs: char[] instead of std::string,
for example. Of course, this still isn't optimized for disk; if
your data set is significantly larger than real memory, and you
start accessing randomly, you're going to page fault like crazy,
and probably end up significantly slower than a classical data
base (which optimize for disk accesses, taking into account the
difference in access times between real memory and disk).

--
James Kanze (GABI Software) email:ja******* **@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientier ter Datenverarbeitu ng
9 place Sémard, 78210 St.-Cyr-l'École, France, [phone]

[Ian Collins]

James Kanze wrote:

On May 15, 8:42 am, Ian Collins <[e-mail] mwrote:

>CMOS wrote:

>>one of the projects im working in currently requires use of ultra
large sized maps, lists, vector, etc. (basically stl containers).
Sizes might grow up to 1000 Million entries. since it is impossible to
have all this data in memory, im planning to implement these
containers to hold data both in memory and disk at the same time.
im not sure this can be achieved using customer allocators and im
wondering if there are any such implementations .

>The short answer is yes, but are you sure you want to?

Are you sure?

I was thinking of the solution you propose in you second paragraph and
the drawbacks you mention were my reason for suggesting a database.

It's probably possible to do something so that
parts of the map are loaded lazily, but functions like
map<>::operator[] and map<>::iterator ::operator* return
references that are required to be real references, and are
guaranteed to be valid as long as the corresponding entry has
not been erased. I think that that more or less pins any
accessed entry in memory, at its original address. Which means
that while you can load lazily (maybe), you cannot drop an entry
from memory once it has been accessed.

One solution that probably is possible, however, is to put the
map in shared memory, backed by a file, using mmap (or its
Windows equivalent). In theory, I think it is possible to even
allow loading it at an arbitrary address; in practice, the one
time I played this game, we loaded at a fixed adress, and left
the pointer type a T*. We also designed the data structures so
that they only contained PODs: char[] instead of std::string,
for example. Of course, this still isn't optimized for disk; if
your data set is significantly larger than real memory, and you
start accessing randomly, you're going to page fault like crazy,
and probably end up significantly slower than a classical data
base (which optimize for disk accesses, taking into account the
difference in access times between real memory and disk).

--
Ian Collins.

[CMOS]

thanks for all the suggessions. i'll be looking at something like
SysBase while investigating the possibility of implementing a
specialized DB.
one other problem im facing in this project is to have millions of
files in the same directory. this might go up to billions
(2000Million) as well.
does any one have any experiance on this type of thing?

[CMOS]

thanks for all the suggessions. i'll be looking at something like
SysBase while investigating the possibility of implementing a
specialized DB.
one other problem im facing in this project is to have millions of
files in the same directory. this might go up to billions
(2000Million) as well.
does any one have any experiance on this type of thing?

[Alf P. Steinbach]

* CMOS:

thanks for all the suggessions. i'll be looking at something like
SysBase while investigating the possibility of implementing a
specialized DB.
one other problem im facing in this project is to have millions of
files in the same directory. this might go up to billions
(2000Million) as well.
does any one have any experiance on this type of thing?

Where do the files come from?

You're leaving us guessing.

I'd guess this is a design for storing collected measurements. Some
sort of automated physical data acquisition. Is that right?

By the way, you should really be asking in e.g. [comp.programmin g],
since questions of design at that level are off-topic in clc++.

Follow-ups set accordingly.

--
A: Because it messes up the order in which people normally read text.
Q: Why is it such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?

[James Kanze]

On May 17, 2:01 pm, CMOS <manu...@millen niumit.comwrote :

thanks for all the suggessions. i'll be looking at something like
SysBase while investigating the possibility of implementing a
specialized DB.
one other problem im facing in this project is to have millions of
files in the same directory. this might go up to billions
(2000Million) as well.
does any one have any experiance on this type of thing?

Yes, but it's very system dependent. At least on some earlier
versions of Unix (and maybe still today---I'm not about to try
it), access becomes very, very slow for anything over a couple
of hundred files.

More generally, I don't think any file system is designed with
this kind of thing in mind. Anytime you need more than a couple
of hundred elements in a flat structure, with rapid access, you
should be thinking in terms of a data base.

--
James Kanze (Gabi Software) email: ja*********@gma il.com
Conseils en informatique orientée objet/
Beratung in objektorientier ter Datenverarbeitu ng
9 place Sémard, 78210 St.-Cyr-l'École, France, [phone]