--- a/src/dwarf2-abbrev.c	Sun Aug 01 23:54:31 2010 +0200
+++ b/src/dwarf2-abbrev.c	Mon Aug 02 00:24:56 2010 +0200
@@ -46,32 +46,25 @@
 {
         uint8_t start_slot = (uint8_t) key % CACHE_SIZE;
         struct cache_entry *begin = &cache->entries[start_slot];
-        struct cache_entry *end = &cache->entries[CACHE_SIZE];
+        struct cache_entry *end = &cache->entries[0];
         struct cache_entry *backup_entry = 0;
         struct cache_entry *entry;
+        int distance;
 
-        cache->time++;
- restart:
-        for (entry = begin; entry != end; entry++) {
-                if (entry->occupied) {
-                        if (entry->key == key) {
-                                /* found slot */
-                                CACHE_DEBUG_PRINTF ("found %d at %d\n", (int)key, i);
-                                entry->last_used = cache->time;
-                                *value = entry->value;
-                                return 1;
-                        } else if (entry->key < key 
-                                   && (backup_entry == 0
-                                       || entry->key > backup_entry->key)) {
-                                backup_entry = entry;
-                        }
+        if (begin->key == key) {
+                /* found slot */
+                CACHE_DEBUG_PRINTF ("found %d\n", (int)key);
+                *value = begin->value;
+                return 1;
+        }
+
+        for (entry = begin, distance = 0; distance < 20 && entry != end; entry--, distance++) {
+                if (entry->occupied &&
+                    backup_entry == 0) {
+                        backup_entry = entry;
+                        break;
                 }
         }
-        if (entry == &cache->entries[CACHE_SIZE]) {
-                end = begin;
-                begin = &cache->entries[0];
-                goto restart;
-        }
         
         /* did not find the key in the cache after looking 
          * at every entry. Try to return the highest
@@ -79,10 +72,9 @@
          * It is stored in backup_slot.
          */
         if (backup_entry != 0) {
-                backup_entry->last_used = cache->time;
                 *value = backup_entry->value;
-                CACHE_DEBUG_PRINTF ("found backup %d for %llu\n", 
-                                    backup_entry->key, key);
+                CACHE_DEBUG_PRINTF ("found backup %d for %llu d=%d\n", 
+                                    backup_entry->key, key, distance);
                 return 1;
         } else {
                 CACHE_DEBUG_PRINTF ("did not find %llu\n", key);
@@ -90,67 +82,18 @@
         }
 }
 
-static inline struct cache_entry *
-cache_search_lru_location (struct cache *cache)
-{
-        struct cache_entry *begin = &cache->entries[0];
-        struct cache_entry *end = &cache->entries[CACHE_SIZE];
-        struct cache_entry *entry;
-        struct cache_entry *lru = begin;
-        uint8_t lru_time = cache->time;
-        for (entry = begin; entry != end; entry++) {
-                if (entry->last_used < lru_time) {
-                        lru_time = entry->last_used;
-                        lru = entry;
-                }
-        }
-        return lru;
-}
-
 static inline void 
 cache_try_add (uint64_t key, uint32_t value, struct cache *cache)
 {
-        uint8_t start_slot = (uint8_t) key % CACHE_SIZE;
-        struct cache_entry *begin = &cache->entries[start_slot];
-        struct cache_entry *end = &cache->entries[CACHE_SIZE];
-        struct cache_entry *entry;
-        struct cache_entry *lru;
+        uint8_t slot = (uint8_t) key % CACHE_SIZE;
+        struct cache_entry *entry = &cache->entries[slot];
 
-        if (begin->value == value) {
-                goto ok;
+        if (entry->occupied && entry->value == value) {
+                return;
         }
-        cache->time++;
- restart:
-        for (entry = begin; entry != end; entry++) {
-                if (!entry->occupied) {
-                        /* reached empty slot 
-                         * add item.
-                         */
-                        CACHE_DEBUG_PRINTF ("add %d start: %d\n", 
-                                            key, start_slot);
-                        entry->key = key;
-                        entry->value = value;
-                        entry->last_used = cache->time;
-                        entry->occupied = 1;
-                        goto ok;
-                }
-        }
-        if (entry == &cache->entries[CACHE_SIZE]) {
-                end = begin;
-                begin = &cache->entries[0];
-                goto restart;
-        }
-
-        /* no empty slot. replace the Least Recently Used 
-         * with this entry.
-         */
-        lru = cache_search_lru_location (cache);
-        lru->key = key;
-        lru->value = value;
-        lru->last_used = cache->time;
-        CACHE_DEBUG_PRINTF ("add full %d\n", key);
- ok:
-        return;
+        entry->key = key;
+        entry->value = value;
+        entry->occupied = 1;
 }
 
 static void

--- a/src/dwarf2-abbrev.h	Sun Aug 01 23:54:31 2010 +0200
+++ b/src/dwarf2-abbrev.h	Mon Aug 02 00:24:56 2010 +0200
@@ -34,19 +34,16 @@
         uint32_t end;   /* end of .debug_abbrev from start of file */
 };
 
-#define CACHE_SIZE (64)
+#define CACHE_SIZE (256)
 struct dwarf2_abbrev_cu {
         uint32_t start; /* offset from start of file */
         uint32_t end;   /* offset from start of file */
         struct cache {
                 struct cache_entry {
                         uint8_t key;
-                        uint8_t last_used;
                         uint8_t occupied;
-                        uint8_t padding;
                         uint32_t value;
                 } entries[CACHE_SIZE];
-                uint8_t time;
         } cache;
 };