Re: [boost] Re: Re: STL applied to disk

From: Wesley W. Terpstra (terpstra_at_[hidden])
Date: 2002-11-19 12:34:21

On Tue, Nov 19, 2002 at 10:38:27AM -0500, David Abrahams wrote:
> "Wesley W. Terpstra" <terpstra_at_[hidden]> writes:
> > So... I am beginning to lean towards the "don't do that" approach where I
> > simply don't allow the user to call member methods on items in the
> > container. (And not let them take pointers) This allows at least the above
> > optimization and a few others (like *i = *j; -- no deserialize&serialize)
> > and probably more I don't forsee yet.
> 
> I haven't been paying attention, but IIUC what you're proposing, these
> things are no longer conforming iterators.
> 
> The way to make random access iterators over disk storage is to build
> an iterator which stores its value_type internally. You can even
> arrange for it to construct the value_type in its internal storage on
> demand, so that it doesn't store anything until it is dereferenced.

I assume you mean they are not iterators because operator -> is broken?
Yes I agree. 
Aside from that however, I believe they do conform to iterators.

What you are proposing however is flawed for several reasons.

If I stored the value_type internally, this will break:

map::iterator i = ...;
map::reference x = *i;
++i;
x = ...; // what is x now pointing at? the wrong record.

Also, if you have two iterators pointing at the same thing, but keeping
distinct value_types internally, expressions like:
        i->set_member_a(j->set_member_b(3) + 2);
will break -- only one of the changes will make it to disk.

---
I know that this could be solved with some sort of:
struct Address
{
	sectorptr_t	sector;
	sectorlen_t	record;
};
struct Object
{
	Observable	observable;
	T		object;
};
std::map<Address, Object> which I keep in for each database.
Then, every time you want to dereference an iterator, you lookup the address
in the table (deserializing if necessary), reference the observable and
return the object. 
When the observable is not_observed, you remove the Object from the table
and reserialize to disk.
The whole question revolves around:
	is the overhead of such a table justified by the benefit of allowing
	member methods to be called on objects within the container.
There are significant costs:
	the overhead of redundant cache
		(it is already cached at the sector level)
	the overhead of indexing the map
		(considerable if you are just deserializing an int)
My current answer is "not justified". But, I am open to persuasion,
especially in the form of an optimized solution.
---
Wes