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

From: David Abrahams (dave_at_[hidden])
Date: 2002-11-19 12:52:19

"Wesley W. Terpstra" <terpstra_at_[hidden]> writes:

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

And operator*.

> Yes I agree.  Aside from that however, I believe they do conform to
> iterators.

So what?

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

That code is already broken if it makes any assumptions about what x
refers to after ++i. Sad but true.

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

You can get around this by dynamically allocating the value_type and
keeping a cache of active values in the container... if it's
important.

<snip>

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

It depends on whether you're advertising STL compatibility or not. If
not, do what ever you like and use a large, loud disclaimer when you
write "iterator" (in quotes) in your documentation. If so, you have to
bite the bullet and make the iterators conform.

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

I think it's early to worry about optimization. Make it work first. An
implementation which lies about its "iterators" is broken.

-- 
                       David Abrahams
   dave_at_[hidden] * http://www.boost-consulting.com
Boost support, enhancements, training, and commercial distribution