Merge lp:~tdfischer/zeitgeist/event-caching into lp:~zeitgeist/zeitgeist/bluebird

[Trever Fischer]

Implements a LRU cache for events, to reduce hitting the database on every request.

[lp:~tdfischer/zeitgeist/event-caching]

422. By Trever Fischer on 2012-03-14

Add files I missed

423. By Trever Fischer on 2012-03-15

Ignore the new test

424. By Trever Fischer on 2012-03-15

Remove the test binary that was accidentally committed

425. By Trever Fischer on 2012-03-15

Fix handling of null events, and use a pre-sized GenericArray to reduce CRITICAL messages

[Siegfried Gevatter (rainct)]

Hi Trever,

Nice work, thanks for working on this!

Some comments:

> max_cache_size = 1024;
We have a (so far unused) constant for this in src/utils.vala: Utils.CACHE_SIZE.

+ uncached_ids.resize(uncached_ids.length+1);
+ uncached_ids[uncached_ids.length-1] = event_ids[i];
You can use "+=" here (which looks nicer and does power-of-two allocations).

+ cache = new EventCache();
                              ^ space
+ for(int i = 0; i < event_ids.length; i++)
     ^ space
And more spaces missing in function declarations in event-cache.vala.

Also, see the comment:

// TODO: Consider if we still want the cache. [...]
// It'd also benchmark it again first, we may have better options
// to enhance the performance of SQLite now, and event processing
// will be faster now being C.

Some numbers about how this affects performance for different queries (cold query vs hot query vs mixed query with and without cache).

review: Needs Fixing

[Trever Fischer (tdfischer)]

Updated. I'll start working on providing some analysis.

[lp:~tdfischer/zeitgeist/event-caching]

426. By Trever Fischer on 2012-03-30

style++, and use automatic array power of two allocation

Unmerged revisions

426. By Trever Fischer on 2012-03-30

style++, and use automatic array power of two allocation

425. By Trever Fischer on 2012-03-15

Fix handling of null events, and use a pre-sized GenericArray to reduce CRITICAL messages

424. By Trever Fischer on 2012-03-15

Remove the test binary that was accidentally committed

423. By Trever Fischer on 2012-03-15

Ignore the new test

422. By Trever Fischer on 2012-03-14

Add files I missed

421. By Trever Fischer on 2012-03-14

Implement LRU event cache

=== modified file '.bzrignore'
--- .bzrignore	2012-02-14 16:57:23 +0000
+++ .bzrignore	2012-03-30 14:51:19 +0000
@@ -68,3 +68,4 @@
 mimetype-test
 marshalling-test
 test/direct/datamodel-test
+test/direct/event-cache-test
 
=== modified file 'extensions/fts++/Makefile.am'
--- extensions/fts++/Makefile.am	2012-02-12 20:17:52 +0000
+++ extensions/fts++/Makefile.am	2012-03-30 14:51:19 +0000
@@ -42,6 +42,7 @@
 	ontology-uris.vala \
 	mimetype.vala \
 	ext-dummies.vala \
+	event-cache.vala \
 	$(NULL)
 
 libzeitgeist_internal_la_SOURCES = \
 
=== added symlink 'extensions/fts++/event-cache.vala'
=== target is u'../../src/event-cache.vala'
=== modified file 'src/Makefile.am'
--- src/Makefile.am	2012-02-15 19:55:59 +0000
+++ src/Makefile.am	2012-03-30 14:51:19 +0000
@@ -48,6 +48,7 @@
 	ontology.vala \
 	ontology-uris.vala \
 	mimetype.vala \
+	event-cache.vala \
 	$(NULL)
 
 zeitgeist_daemon_SOURCES = \
 
=== modified file 'src/db-reader.vala'
--- src/db-reader.vala	2012-03-19 19:56:38 +0000
+++ src/db-reader.vala	2012-03-30 14:51:19 +0000
@@ -45,6 +45,8 @@
     protected TableLookup mimetypes_table;
     protected TableLookup actors_table;
 
+    protected EventCache cache;
+
     public DbReader () throws EngineError
     {
         Object (database: new Zeitgeist.SQLite.Database.read_only ());
@@ -59,6 +61,8 @@
         manifestations_table = new TableLookup (database, "manifestation");
         mimetypes_table = new TableLookup (database, "mimetype");
         actors_table = new TableLookup (database, "actor");
+
+        cache = new EventCache ();
     }
 
     protected Event get_event_from_row (Sqlite.Statement stmt, uint32 event_id)
@@ -114,10 +118,26 @@
         //  to enhance the performance of SQLite now, and event processing
         //  will be faster now being C.
 
+        var results = new GenericArray<Event?> ();
+        results.length = event_ids.length;
         if (event_ids.length == 0)
-            return new GenericArray<Event?> ();
-
-        var sql_event_ids = database.get_sql_string_from_event_ids (event_ids);
+            return results;
+
+        uint32[] uncached_ids = new uint32[0];
+        for (int i = 0; i < event_ids.length; i++)
+        {
+            Event? e = cache.get_event (event_ids[i]);
+            if (e != null) {
+                results.set(i, e);
+            } else {
+                uncached_ids += event_ids[i];
+            }
+        }
+
+        if (uncached_ids.length == 0)
+            return results;
+
+        var sql_event_ids = database.get_sql_string_from_event_ids (uncached_ids);
         string sql = """
             SELECT * FROM event_view
             WHERE id IN (%s)
@@ -149,12 +169,14 @@
         }
 
         // Sort events according to the sequence of event_ids
-        var results = new GenericArray<Event?> ();
         results.length = event_ids.length;
         int i = 0;
         foreach (var id in event_ids)
         {
-            results.set(i++, events.lookup (id));
+            Event e = events.lookup (id);
+            if (e != null)
+                cache.cache_event (e);
+            results.set(i++, e);
         }
 
         return results;
 
=== added file 'src/event-cache.vala'
--- src/event-cache.vala	1970-01-01 00:00:00 +0000
+++ src/event-cache.vala	2012-03-30 14:51:19 +0000
@@ -0,0 +1,77 @@
+/* event-cache.vala
+ *
+ * Copyright © 2012 Collabora Ltd.
+ *             By Trever Fischer <[e-mail]>
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU Lesser General Public License as published by
+ * the Free Software Foundation, either version 2.1 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public License
+ * along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ *
+ */
+
+using Zeitgeist;
+
+namespace Zeitgeist
+{
+public class EventCache : Object
+{
+
+    private HashTable<uint32?, Event> cache_table;
+    private Queue<uint32> lru_queue;
+    private uint max_cache_size;
+
+    construct
+    {
+        cache_table = new HashTable<uint32?, Event> (int_hash, int_equal);
+        lru_queue = new Queue<uint32>();
+        max_cache_size = Utils.CACHE_SIZE;
+    }
+
+    public Event? get_event(uint32 id)
+    {
+        Event? e = cache_table.get (id);
+        if (e != null)
+        {
+            lru_queue.remove_all (id);
+            lru_queue.push_tail (id);
+        }
+        return e;
+    }
+
+    public void cache_event(Event e)
+    {
+        cache_table.set (e.id, e);
+        lru_queue.remove_all (e.id);
+        lru_queue.push_tail (e.id);
+
+        while (lru_queue.length > max_cache_size)
+        {
+            uint32 target = lru_queue.pop_head ();
+            cache_table.remove (target);
+        }
+    }
+
+    public uint size
+    {
+        get { return lru_queue.length; }
+    }
+
+    public uint max_size
+    {
+        get { return max_cache_size; }
+        set { max_cache_size = value; }
+    }
+}
+
+}
+
+// vim:expandtab:ts=4:sw=4
 
=== modified file 'test/direct/Makefile.am'
--- test/direct/Makefile.am	2012-02-15 18:55:42 +0000
+++ test/direct/Makefile.am	2012-03-30 14:51:19 +0000
@@ -11,6 +11,7 @@
 
 TESTS = \
 	datamodel-test \
+	event-cache-test \
 	marshalling-test \
 	mimetype-test \
 	query-operators-test \
@@ -36,8 +37,12 @@
 	$(top_srcdir)/src/ontology.vala \
 	$(top_srcdir)/src/ontology-uris.vala \
 	$(top_srcdir)/src/mimetype.vala \
+	$(top_srcdir)/src/event-cache.vala \
 	$(NULL)
 
+event-cache-test: event-cache-test.vala $(SRC_FILES)
+	$(VALA_V)$(VALAC) $(VALAFLAGS) -o $@ $^
+
 datamodel-test: datamodel-test.vala $(SRC_FILES)
 	$(VALA_V)$(VALAC) $(VALAFLAGS) -o $@ $^
 
@@ -66,11 +71,13 @@
 	query-operators-test \
 	table-lookup-test \
 	where-clause-test \
+	event-cache-test \
 	$(NULL)
 
 EXTRA_DIST = \
 	assertions.vapi \
 	datamodel-test.vala \
+	event-cache-test.vala \
 	marshalling-test.vala \
 	mimetype-test.vala \
 	query-operators-test.vala \
 
=== added file 'test/direct/event-cache-test.vala'
--- test/direct/event-cache-test.vala	1970-01-01 00:00:00 +0000
+++ test/direct/event-cache-test.vala	2012-03-30 14:51:19 +0000
@@ -0,0 +1,84 @@
+/* event-cache-test.vala
+ *
+ * Copyright © 2012 Collabora Ltd.
+ *             By Trever Fischer <[e-mail]>
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU Lesser General Public License as published by
+ * the Free Software Foundation, either version 2.1 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public License
+ * along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ *
+ */
+
+using Zeitgeist;
+using Assertions;
+
+int main (string[] args)
+{
+    Test.init (ref args);
+    Log.set_always_fatal (LogLevelFlags.LEVEL_CRITICAL);
+
+    Test.add_func("/EventCache/basic", basic_test);
+    Test.add_func("/EventCache/size", size_test);
+    Test.add_func("/EventCache/expiration", expiration_test);
+
+    return Test.run ();
+}
+
+public void basic_test ()
+{
+    EventCache c = new EventCache ();
+    for (int i = 0; i<1024; i++)
+    {
+        Event e = new Event();
+        e.id = i;
+        c.cache_event (e);
+    }
+    assert (c.size == 1024);
+}
+
+public void size_test ()
+{
+    EventCache c = new EventCache ();
+    c.max_size = 5;
+    for (int i = 0; i<2048; i++)
+    {
+        Event e = new Event();
+        e.id = i;
+        c.cache_event (e);
+    }
+
+    assert (c.size == 5);
+}
+
+public void expiration_test ()
+{
+    EventCache c = new EventCache ();
+    c.max_size = 5;
+    for (int i = 0; i < 5; i++)
+    {
+        Event e = new Event();
+        e.id = i;
+        c.cache_event (e);
+    }
+
+    // Refresh the LRU stamp for #0, so #30 expires #1
+    c.get_event(0);
+    Event e = new Event();
+    e.id = 30;
+    c.cache_event (e);
+
+    assert(c.get_event(0) != null);
+    assert(c.get_event(1) == null);
+    assert(c.get_event(30) != null);
+}
+
+// vim:expandtab:ts=4:sw=4