RE: Number 9 of the mytest summary store: writing things

[Philip Van Hoof <spam pvanhoof be>]

On Mon, 2008-01-07 at 11:02 +0200, Dirk-Jan Binnema nokia com wrote:

> That's a pretty big assumption; do you have the numbers to support that?
> I don't see how hits for "dog" would necessarily be close in time

I think ... (subjective, indeed)

Most people search for situations and persons. Like: when did I send
that invoice to my customer again? So he searches for that customer's
name. All exchanges with the customer are often grouped in time (bursts
of exchanges, for example a few weeks of discussing things and then
months of nothing about that subject).

Note that it's also not extremely important if the results are not close
together. It's just more ideal: less pages need to be mapped, less open
filedescriptors (less mapped summary blocks needed), etc etc

Opening a summary block and scanning it in takes ~ 2 seconds for 50,000
items with today's implementation. That's because the entire file needs
to be seeked / touched: a lot of pages are being faulted just to find
all the string offsets while loading a folder.

The same operation takes < 0.2 seconds for this test implementation
(that's because it only needs to scan the index_0.idx file, which is a
sequential file). And I can even improve the read-speed by not using
fscanf() but in stead by reading the integers as four bytes straight
from the file.

The string locations don't have to be found anymore: they are in that
sequential index file already. This is why it's a lot faster (so it's
not faster by accident: this is a performance problem in the current
implementation, and these experiments are a solution).


So:

index_0.idx : sequential file with all the string offsets for each item
data_0.mmap : strings (unique and sorted on frequency used)
flags_0.idx : sequential file with the flags for each item

Loading a folder means:

Step one: 

* this is extremely fast and done by the kernel

	mmap(data_0.mmap) 

Step two: 

* this takes < 0.2 seconds

	while (!feof(index_fd) && !(feof (flags_fd)) {
	   fscanf (index_fd, "%d %d ..", &offset1, &offset2, ...);
	   fscanf (flags_fd, "%d", &flags);
	}

Step three: 

 * done


Note:

A database can't really make this faster, as it needs to parse the SQL
syntax, it needs to make an execution path, it needs to read the data,
it needs to copy it to its library layer, the library needs to take the
data out of its string encapsulation. - databases are no magic -

> > o. When adding summary items to the summary (which will 
> > select a summary
> >    block where the item will be added to using the requested sequence
> >    number), the caller must attempt to avoid string duplicates for the
> >    CC and TO fields of the items by sorting the addresses in the comma
> >    separated strings of the items. Currently will the experimental
> >    example do this for you. This further reduces VmRss as you'll have
> >    singled-out more data as duplicate and made more data unique in
> >    memory this way.
> 
> Obviously, you will save a bit of memory, but as I've shown before,
> it's not very much in (ie. even with a 1000 duplicate addresses,  you'd
> save only 20k)

This is not (only) about memory duplication, but about VmRss. Storing
addresses sorted causes more duplicates, which causes that we can reuse
the same strings more often, which improves locality of data, which
means that we'll have less page faults, which lessens VmRss.

Actually, it's not even "just" VmRss that is important. For speed and
low memory consumption at the same time you want to reduce "page
faults", period: If by increasing VmRss a little bit you reduce the
amount of page faults, go for that.

An example: putting the memory of the SummaryItem struct instances in a
mapped file will just result in the file's mapping being completely in
VmRss anyway. But if not (if swapped out), you'll get more page faults
and therefore a slower waking up application (after inactivity).

So you just malloc() those ... (or use gslice, of course).


> On the other hand, couldn't this negatively impact performance? Right
> now, strings for a certain message can be kept together, and maybe
> use the cache in a bit better way.

> Also, determining what is a non-unique string will take time, and a code 
> complexity.

Complexity
----------

That's why we're doing these experiments. They are working and the code
isn't very complex (putting a string in a hashtable is not complex, and
perfect for making strings in a list of strings unique).

Here's my POV on "complexity": 

Don't make things more complex than needed, but also DON'T MAKE THEM
LESS COMPLEX.

There's a big danger in constantly trying to make things simplistic
simple if the problem domain isn't simple. Your solution will because of
its simplicity not solve the problem, but in stead it will offer a
lesser solution and as a result only partially solve the problem.

What happens next are hacks and workarounds to make the use-case still
actually work for the user or customer.

Final result: a far more complex final solution with hacks, workarounds
rotten code, cruft, crap, more bugs, more time to develop it and a
competitor who'll outperform you several times in both code elegance,
performance and stability.

A good example: the internal queue for async operations. This solution
is simpler than what we had first. But it's definitely far more stable
and far more elegant, and it didn't influence performance a lot
(actually, since threads need to be started less often, it's probably
better performing too).


Time and performance
-------------------- 

Storing duplicate strings takes more time than sorting a group of
strings, making them unique and then storing the unique strings.

That's because writing to disk is slower than sorting in memory.

So although determining what is a non-unique string takes time, we are
saving more time by doing it because we don't have to write the
duplicates.

This is measured, by the way.

Although this was by accident. (I didn't expect it to be faster)


> It's hard to say what the end result of all this, let's be careful
> and extremely skeptical :)

Always :)


-- 
Philip Van Hoof, freelance software developer
home: me at pvanhoof dot be 
gnome: pvanhoof at gnome dot org 
http://pvanhoof.be/blog
http://codeminded.be