Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > maps to hold ultra large data sets using customer allocators to allocate disk space rather than main memory

Reply
Thread Tools

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

 
 
CMOS
Guest
Posts: n/a
 
      05-15-2007
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

 
Reply With Quote
 
 
 
 
Alf P. Steinbach
Guest
Posts: n/a
 
      05-15-2007
* 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?
 
Reply With Quote
 
 
 
 
Ian Collins
Guest
Posts: n/a
 
      05-15-2007
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.
 
Reply With Quote
 
CMOS
Guest
Posts: n/a
 
      05-15-2007
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

 
Reply With Quote
 
Ian Collins
Guest
Posts: n/a
 
      05-15-2007
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.
 
Reply With Quote
 
CMOS
Guest
Posts: n/a
 
      05-15-2007
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.

 
Reply With Quote
 
Gianni Mariani
Guest
Posts: n/a
 
      05-15-2007
On May 15, 4:12 pm, CMOS <(E-Mail Removed)> 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.
>
> thank you


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

Either one should do the job.

 
Reply With Quote
 
Ian Collins
Guest
Posts: n/a
 
      05-15-2007
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.
 
Reply With Quote
 
meagar
Guest
Posts: n/a
 
      05-15-2007
On May 15, 1:12 am, CMOS <(E-Mail Removed)> 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.
>
> 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.

 
Reply With Quote
 
James Kanze
Guest
Posts: n/a
 
      05-16-2007
On May 15, 9:04 am, CMOS <(E-Mail Removed)> wrote:
> 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:(E-Mail Removed)
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34

 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Need to Allocate more space than size_t ramasubramanian.rahul@gmail.com C Programming 20 11-15-2006 05:42 PM
Main Advantages i get when i do a stand alone app in .Net rather than in VB. Punya Narra ASP .Net 5 02-17-2004 12:02 PM
Sandisk Ultra II, "new" Ultra, "original " Ultra Eberhard Funke Digital Photography 0 01-13-2004 04:35 PM
Getting "not enough disk space error" when there is plenty of disk space Jas Shultz ASP .Net 0 12-03-2003 05:07 PM



Advertisments