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

[Alf P. Steinbach]

* 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 .

A few GBytes of data isn't that much, really, if you have the hardware
to match. However, from your comment about "customer (sic) allocators",
and simply from the fact that you're seeking advice here, I'm reasonably
sure that this is not a million-dollar budget project, but rather a
student project, and that the requirement of billions of entries stems
from bad design, and is not an inherent requirement of the problem
you're trying to solve. So do tell about the problem, not how you're
envisioning solving it; perhaps we can suggest better ways.

--
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?

[Ian Collins]

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?

--
Ian Collins.

[CMOS]

NOTED: Custom Allocator: sorry.

the problem is to index 10 Billion records of certain type using a
given field. field type might be a number, string, date, etc.
and to query the results for fast retrieval.

thanks

[Ian Collins]

CMOS wrote:

NOTED: Custom Allocator: sorry.

the problem is to index 10 Billion records of certain type using a
given field. field type might be a number, string, date, etc.
and to query the results for fast retrieval.

Why not just use a database, which will have been optimised for this task?

--
Ian Collins.

[CMOS]

a generic DB's performance will not be enough and i do not need it to
support any data modifications, transactions, etc which will slow down
operation.
the only requrement is to Insert data and query and delete records
using keys. no need of SQL interface either.

[Gianni Mariani]

On May 15, 4:12 pm, CMOS <manu...@millen niumit.comwrote :

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

http://www.sqlite.org/
http://www.postgresql.org/

Either one should do the job.

[Ian Collins]

CMOS wrote:

Please quote enough context for your reply to make sense.

a generic DB's performance will not be enough and i do not need it to
support any data modifications, transactions, etc which will slow down
operation.
the only requrement is to Insert data and query and delete records
using keys. no need of SQL interface either.

Well I'd still use one, unless I had a real performance issue. Even
then my first action would be upgrade the hardware!

--
Ian Collins.

[meagar]

On May 15, 1:12 am, CMOS <manu...@millen niumit.comwrote :

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

I don't think you appreciate how slow it will be to search a billion
records without loading the bulk of them into RAM. I mean, you're
going to be swapping the entire file in and out of RAM anyways, as the
OS will be buffering the file in memory anyways.

You might consider storing the records in a file, and then creating a
separate indexing map which just contains the unique identifying
fields from the object, mapped to an byte-offset leading to the record
in the file.

[James Kanze]

On May 15, 9:04 am, CMOS <manu...@millen niumit.comwrote :

a generic DB's performance will not be enough and i do not need it to
support any data modifications, transactions, etc which will slow down
operation.
the only requrement is to Insert data and query and delete records
using keys. no need of SQL interface either.

Using std::map with allocators for data on disk will *not*
result in better performance than a commercial data base.
Commercial data bases have invested hundreds of man years in
optimizing their accesses. At least one commercial vendor,
SyBase, has a variant of their data base optimized for exactly
this sort of application: updates only in batch, no
transactions, but very fast read access for very, very large
data sets. And all commercial data bases know how to maintain
indexes for multiple fields, in a fashion optimized for disk (B+
trees or hash tables, rather than the classical binary tree
typically used by std::map.) It may be possible to do better
than the commercial data bases for a specialized application,
but to do so will require very special custom code (and not just
std::map with a special allocator), and probably something up of
ten man years development time.

In answer to your question, however, I have my doubts as to
whether it is even possible. The accessors to std::map return
references, and these are required by the standard to be real
references. Which means that user code will have references
into your in memory data which you cannot track, which in turn
means that you cannot know when you can release the in memory
data---any data, once accessed, must be maintained in memory for
all time.

--
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]