S4 development

May 31, 2010

Benchmark update

Filed under: Uncategorized — Sivert Berg @ 12:35

It turns out Erik Massop (nesciens) had some code to speedup SQL queries in his repository. Here it is compared to the old SQL code and S4 midb:
UPDATE: Erik pushed some new code, making some queries faster. The queries that saw improvement are marked in red. The rest of the queries performed the same as the old code. One change in the new code is that it keeps the SQLite connection alive instead of creating a new one for every query. The difference can best be seen on a short query like “one”:

The old code:

query_infos took: 878
session took:     827
select took:      386

Compared to the new code:

query_infos took: 432
session took:     370
select took:      365

We see that the select takes about the same time, but the whole session takes about twice as long with the old code. For large queries like “*” the difference is less visible:

The old code:

query_infos took: 228048
session took:     228024
select took:      227569

Compared to the new code:

query_infos took: 224097
session took:     224062
select took:      224052
Query SQL Old SQL Experiment S4 midb
Avg (µs) S (µs) Avg (µs) S (µs) Avg (µs) S (µs)
“one” 180115.3 ~5521.6 326.0 ~8.9 127.7 ~3.7
“*” 365540.5 ~7049.7 225482.8 ~1011.7 148165.8 ~3209.5
“artist:metallica” 6864.2 ~214.3 3755.7 ~16.7 3336.5 ~219.5
“tracknr>20” 30378.6 ~789.9 14682.2 ~214.8 1871.7 ~132.7
“tracknr>30” 27624.5 ~1372.5 10996.5 ~23.3 236.1 ~7.5
“+comment” 238729.9 ~7028.3 73566.2 ~1553.5 58894.9 ~2003.7
“tracknr:4” OR “artist~foo” AND NOT “artist:weezer” 188794.7 ~4773.8 49245.6 ~1210.9 18785.8 ~638.8

As we can see most queries are getting a nice speedup. Most notably “one” which is about 500 (!) times faster. But also “+comment” (3.2 times faster) and that long last query (3.8 times faster) gets a nice boost. The only one getting slower is “*” (taking over 2 seconds). S4 is still faster than SQL, but all the SQL queries (with the exception of “*”) are under 100 milliseconds on a moderately sized media library (~10,000 songs).

Advertisements

May 29, 2010

Benchmarks

Filed under: Uncategorized — Sivert Berg @ 18:44

I finally had time to run a few benchmarks. I wanted to measure how the different back-ends compared to each other in query performance, memory consumption and disk usage. The back-ends being compared are SQLite (the current back-end used in xmms2-devel), S4 mmap (the “old” S4 back-end) and S4 midb (a new experimental S4 back-end).

Just to cover my back: I do not have much experience with benchmarks, and I am in no way an objective observer (slight bias towards S4, me?). If you see something that seems wrong, let me know; I probably made a mistake.

Query performance

First we will look at query performance. This is perhaps the factor that is most visible to the end user. The time measured is the time spent inside the xmms_collection_client_query_infos. It was measured by running gettimeofday at the beginning and end of the function and printing the difference in microseconds. I also used a slightly modified nyxmms2 that uses xmms_coll_query_infos instead of xmms_coll_query_ids.

So, to the results. The table shows the average time used in the query (calculated by \overline{X}=\frac{1}{n}\sum_{i=1}^n X_i where X_i is the time used on the i’th run) and the sample standard deviation (calculated by S^2=\frac{1}{n-1}\sum_{i=1}^n (X_i - \overline{X})^2 and then taking the square-root to get S). n was 10 for all benchmarks. The last column is the average time that SQLite used divided by the average time S4 midb used.

Query SQLite S4 mmap S4 midb SQLite / midb
Avg (µs) S (µs) Avg (µs) S (µs) Avg (µs) S (µs)
“one” 180115.3 ~5521.6 203.2 ~5.2 127.7 ~3.7 ~1410
“*” 365540.5 ~7049.7 286972.0 ~5489.7 148165.8 ~3209.5 ~2.47
“artist:metallica” 6864.2 ~214.3 5377.6 ~175.7 3336.5 ~219.5 ~2.06
“tracknr>20” 30378.6 ~789.9 2885.1 ~89.4 1871.7 ~132.7 ~16.23
“tracknr>30” 27624.5 ~1372.5 454.7 ~77.0 236.1 ~7.5 ~117.0
“+comment” 238729.9 ~7028.3 106268.0 ~3277.4 58894.9 ~2003.7 ~4.05
“tracknr:4” OR “artist~foo” AND NOT “artist:weezer” 188794.7 ~4773.8 26407.7 ~793.9 18785.8 ~638.8 ~10.05

As we can see S4 is faster in all cases, ranging from about 2 to over a 1000 times faster. Why “one” is so much slower on SQLite I don’t know, could be inefficient SQL query, could be something else. Also worth noting is that S4 is mostly bound by the size of the result set. Queries resulting in small result sets (“one” for example) gives short query times. I’ll get back to why later.

Memory consumption

To get good performance S4 trades memory for speed. The big question is if the trade-off is worth it. For now we will settle for finding out exactly how much memory the different back-ends use. Memory consumption was measured by using massif, a valgrind tool. The back-ends were run two times, once by just starting up and shutting down and another time with a query for “*” before shutting down. That way I hope to visualize idle memory usage versus usage when searching. All numbers are in MiB.

SQLite S4 mmap S4 midb
Idle Search Idle Search Idle Search
10.43 17.77 1.13 10.59 23.79 32.56

As we can see both S4 implementation adds about 9 MiB when searching compared to the 7 MiB SQLite add. Also it may seem like S4 with mmap is the big winner here, but what massif does not show is shared memory, the kind mmap uses. If that had been counted in we would have added about 22 MiB to S4 mmap, bringing it up to about the same memory usage as S4 midb. So with a media library with 9,361 entries S4 uses a little over twice the memory SQLite uses at idle.

Disk usage

Finally, the one most people probably will not care about with today’s abundance of disk space: disk usage. It’s simply the size of the datafile.

SQLite S4 mmap S4 midb
41.5 MiB 21.7 MiB 5.4 MiB

Summary

In terms of performance and disk space S4 (especially the midb version) is the clear winner, but it eats up about twice as much memory compared to SQLite. Fair tradeoff? Maybe for a 10,000 entry media library, but what about one with 100,000 entries? We would probably see memory usage around 200 MiB.

A note on S4 query performance

As I said earlier S4’s query speed is mostly bound by the size of the result set. To see why we have to dig a little. Running XMMS2 in Callgrind (another Valgrind tool) is a nice way to find bottlenecks and hotspots. Opening the generated callgrind.out file in KCachegrind reveals a few interesting things:

As we can see xmms_medialib_query_ids (the function calling s4_query) only contribute 3.64% of the running time of the query. The rest of the time is spent fetching the properties (artist, album, …) of the entries we found in the query and inserting them into the dictionary we return. We see that _entry_propery_get_ is called 28,000 times. The media library this was run on has about 500,000 relationships (a relationship is an entry-to-entry mapping, for example (“songid”, 1) -> (“title”, “One”)). Using B+ leaves with room for 101 entries and a fill rate of 50% (it was measured to be around 53%, a bit away from the normally assumed 67% for B+ trees) this gives about 10,000 B+ leaves. A simple traversal of the 10,000 leaves would probably be faster than calling _entry_property_get_ 28,000 times. An observation well worth taking into account when we design the S4 query layer.

May 24, 2010

Hey!

Filed under: Uncategorized — Sivert Berg @ 18:33

Summer is here, and we all know what that means: GSoC and hack time! This year I will try to document the progress here. Who am I? I am a 22 year old computer science student from Norway attending GSoC for the second time. Once again I was given a chance to work on XMMS2 and S4. It is off to a slow start at first because of some exams, but after June 4th it is full speed ahead. As you may know my project this year involves developing a new database backend called S4 for XMMS2. The project will be mentored by Sébastien Cevey. Some of goals of this year’s project is

  • Proper support for source preferences
  • A standalone S4 query layer
  • Coll 2.0 support

To keep track of time we have set up some milestones with associated deadlines. The first one coming up at June 6th is to have a benchmark set up so we can track performance against the old database, but also against itself as we do changes to see if they are worth it.

I cheated a little and started early. The last week I have been trying a new approach in S4. Instead of storing the index data structures on disk as before we build them on startup. The start up takes a little longer (about 0.5 seconds on a media library with 10,000 entries), but otherwise it seems to perform better or on par with the old code using mmap. With this new approach we will hopefully get a more reliable database, smaller on disk file and some performance improvements. A more thorough analysis will be provided when I have time to run some proper benchmarks.

Happy hacking everyone!

Blog at WordPress.com.