Re: [Evolution-hackers] Moving the struct instance heap space to mmap

On 08/09/06, Philip Van Hoof <[email protected]> wrote:
>
> On Fri, 2006-09-08 at 12:44 +0930, Michael Zucchi wrote:
>
> > Hmm, will it really reduce memory usage though?  I'm not so sure.
> > Remember that although the summary file contains all strings on disk,
> > in memory they are actually unique-ized.  For a lot of load-types
> > (e.g. mailing lists), this saves a trememdous amount of memory - even
> > after all the overhead of the hashtable to manage it.  Address and
> > subject strings in particular.  And a mmap file isn't terribly
> > different to performance to malloc'd memory - once the latter is
> > setup, in both cases the kernel is the one loading it off disk (swap,
> > or filesystem).
>
> With the offsets in a different index mmap I can do the same trick of
> course. E.g. let the offset of two fields be the same (let them point to
> a uniqified version of the string, for example the first).
>
> It will indeed be tricky when writing out the summary and index to
> support this. But not impossible. Hard ... is fun :). If it wouldn't be
> hard, it wouldn't be a challenge, lots of our community members wouldn't
> be interested in writing it ;-)
>
> I am. I of course do have priorities for tinymail and other projects.
> But this being one of those funky ideas that I can't get rid of in my
> head, sorts it higher in my prio-list (else I go nuts).
>
> > (an mmap file IS just memory, so if "mmap'd file size + in-memory
> > support tables" > "in-memory version", then you haven't generally won
> > - even if 'ps' shows you have).
>
> I agree but a little but: An mmap can (and often will) be swapped in and
> swapped out by the kernel. It, in general, knows better, than the
> application developer possibly can, when it's a good idea to swap pages
> in and out of mmaps on the system.
>
> My opinion is that it's a particular interesting memory technique on
> mobile devices. Mobile device users often don't care a lot that
> switching between applications takes a few milliseconds before the
> recently switched-to application becomes usable (the swap-in happened).
>
> It can also be shared if multiple E-mail clients do things with the same
> summary files. I agree this is uncommon but on large installations --
> e.g. servers that run a lot instances of the E-mail client with a lot
> shared folders or something like that -- this might be a significant
> improvement. An application like Evolution can probably be adapted to
> figure out about shared folders. Or an admin can be taught to set
> symbolic links to the cache folders of shared accounts as a work-around
> that can be used already (with some inotify magic that will reload the
> summaries of folders of which the summary file got altered by another
> process: for example respond with a mremap in the notified process).


Multiple concurrent access is i guess, a different issue.  Also quite a
difficult one to get right - coherency and whatnot.  I would expect most
server-type installations to use more of a database-type thing anyway.

> Note also that all of the summary items, and all of the strings thus
> > stored, are using special allocators which reduce - significantly -
> > the overhead of malloc, on these small allocations.  In earlier
> > versions I tried a different string allocator for each messageinfo
> > which mimicks much of what you're doing here, but in memory.  Strings
> > were stored in an array structure, but I only stored a single pointer
> > to the base of the array, and packed the strings into a NUL separated
> > right-sized buffer, and searched each time I needed to access them,
> > overhead was only about 5 bytes (pointer to the 'array' plus an array
> > 'limit').   Performance was fine, but memory usage was significantly
> > larger than the current model, where strings are 'unique-ized' - like
> > 30% or more iirc.
>
> True. And we can mimic this behaviour with mmaps too. I do agree it
> would be complex. Especially in the current Camel design. That's why we
> need people like you, Michael, to help us develop the disk summary
> concept ;-)
>
> My opinion is that with a good design, all complex programming concepts
> become simple, understandable, maintainable and doable.
>
> KISS is too often used by people who have no f. idea what software
> development is about. KISS is not "doing everything in Python" or "don't
> type more than 5 lines per algorithm".


Hmm, well I think camel is a bit too complicated. It makes it difficult to
implement backends for the interface.  Well, maybe a little bit more
difficult than need be.  But I suppose not many mail clients try to throw
100K+ message folders at a treeview, and expect it not to use a lot of
memory.

I'm a supporter of splitting complex things up in as much simple pieces
> as needed to make all of the pieces understandable. Descartes was the
> dude that taught us that (other than that, I'm much more into Socrates
> by the way).
>
> My point of this dialog: too complex doesn't exist. We've put a few
> dudes on the moon and build technology that splits atoms. We, humans,
> are designed to overcome complexity.


But if it's too complex to use or maintain, then it is more wasted effort.
I'm becomming much lazier in my older-age perhaps!

> Having extra indices on disk - you're really just writing a datbase
> > table - and all of the associated complexity, consistency and
> > coherency issues that implies.  And unless you do something 'proper'
> > like a btree with a unique key, you're going to have to end up storing
> > plenty of extra support stuff in memory anyway, e.g. a hashtable to
> > find items by uid, the sorted list of messages for the view, and so
> > on.
>
> Finding the items would be done by calculating the offset in the index,
> which can be done each time access to one of its members is needed. I
> wouldn't use the uid but would use a "nth" integer. The uid, being
> fixed-sized, can one of the members in the index. Thus making it
> possible to search for the uid in this index (should be rather fast, in
> an mmap it's probably as fast as searching it in a typical hashtable).


Nup, no way.  Unless you layer some sort of index ontop of it, a linear
search will always be a linear search, and it simply wont scale.  e.g. you
need something like a b-tree.  Even the camel-index stuff uses a partition
table - an extensible hash algorithm, which is about as simple a disk-based
index as you can get, and that's quite a lot of pain (well, fixed-length
keys would remove a lot of its pain, but not all of it).  But it doesn't
have the nice locality of reference properties you get with trees.  Also
note that any sort of index takes up more space, and becomes a major issue
to keep in sync with concurrent access or corruption.

> We did a lot to reduce per-message overhead at the camel level, but
> > its an area of diminishing returns - the ui table view will still take
> > as much memory, etc.
>
> Aha but that can also be reduced if you develop a model that disposes
> the rows that become invisible. With fixed-row and fixed-width and
> implemented row_unref of a custom GtkTreeModel, you can already do
> something like this with GtkTreeView. I'm sure ETable and its model type
> can be adapted (or already are) to support something like this too.


Maybe gtktreeview changed since i last looked at it.  It was rather slow
too, iirc.  There's only so much virtualisation you can do with tree's
anyway, some of the data you need all of the other data to calculate -
unless you keep another on-disk index in 'tree sort' order, and virtualise
even that.

This was something I was thinking about doing with the disksummary stuff,
but i couldn't think of a suitable algorithm to do it.  i.e. as well as the
'vfolder indices, you could add a 'tree' index.  Then you could just iterate
through that linearly to easily produce a visible tree, but only ever have
to instantiate or load the rows of data you're looking at.  Lots of display
scalability, but possibly something that would take a lot of overhead to
create and maintain (particularly if you then wanted to sort it in different
ways).  And it might take more over-all space than doing things in memory
directly - which i presume is an issue with mobile devices.

I suppose you could still generate the index in-memory but only use the
hashes of the message-id and the references (and maybe the subject) using a
single-scan of the index, which would reduce the amount of memory consumed
in that step, at least.

Tinymail is suitable and tested to do this (with GtkTreeView) already.
>
> I tested this principle with the Camel POP provider that doesn't have
> support for summaries. What I did was load CamelMimeMessage instances
> for each row that became visible. It worked, yet per row consumed a
> CamelMimeMessage: an enormous amount of memory (compared to a summary
> item). What didn't work was, of course, sorting. Because instantiating
> CamelMimeMessage instances for each to-sort item, took days.


Yeah i think the way camelpop works isn't the best.  If i were to do it
again, i'd change the object model around a bit.

Instead of provider -> store | transport
I'd probably have some sort of
provider -> host { store | transport | pobox }

And a pobox would be for pop, 'local delivery' and the like, where you just
pickup new mail.  host is like 'store' or 'transport', but having two
separate ones like camel does now just messes things up when they're both
the same connection (the hacks in the groupwise backend for example).

And yes, sorting is one of the major reasons we did stuff in memory - with
tree's you gotta load everything anyway - again, unless you maintain a
separate index, and a more novel tree driver.  But you've always got that
memory/performance/complexity trade-off to make.

But the CamelMimeMessage instances of invisible rows weren't allocated.
> Only the visible ones. Which kept memory consumption of tinymail below
> 10M for a 15,000 messages POP folder (valgrind measured). This wasn't
> using the mmap concept, which in principle does more or less the same
> with the summary data (but then using 4k pages in the kernel).
>
> Viewing and scrolling, using this implementation, was already fast
> enough on a mobile device like the Nokia 770. I'm not going to call is
> "snappy" fast. Just "fast enough" or "acceptable fast".


I dunno, most portable devices i've used feel like shit - somehow 'fast
enough to just use' is fast enough these days!

I am now, like Evolution, going to use the MBOX provider for this in
> tinymail. This support for POP without a summary, was indeed a proof of
> concept in tinymail.
>
>
> Thanks a lot for your point of view Michael. I value it.


 Well you've piqued my interest ever-so-slightly in mail things again, but
I'm not sure - i'm not sure I really want to get back into coding it again,
at least.  It would be more fun writing something a-new than trying to fix
something else, and particularly having to worry about client compatability.

_______________________________________________
Performance-list mailing list
[email protected]
http://mail.gnome.org/mailman/listinfo/performance-list