From 01307b2cc90abd9a218d38cfe9520bad176bb9db Mon Sep 17 00:00:00 2001 From: Aaron Schulz Date: Fri, 22 Sep 2017 18:26:50 +0200 Subject: [PATCH] Allow two-queue style insertion in MapCacheLRU Change-Id: I1cd98ea8965b51e43371efd990fb9302bb507928 --- includes/libs/MapCacheLRU.php | 46 ++++++- .../phpunit/includes/libs/MapCacheLRUTest.php | 114 ++++++++++++++++++ 2 files changed, 156 insertions(+), 4 deletions(-) create mode 100644 tests/phpunit/includes/libs/MapCacheLRUTest.php diff --git a/includes/libs/MapCacheLRU.php b/includes/libs/MapCacheLRU.php index c92769fc4e..553315f23a 100644 --- a/includes/libs/MapCacheLRU.php +++ b/includes/libs/MapCacheLRU.php @@ -48,16 +48,45 @@ class MapCacheLRU { $this->maxCacheKeys = $maxKeys; } + /** + * @param array $values Key/value map in order of increasingly recent access + * @param int $maxKeys + * @return MapCacheLRU + * @since 1.30 + */ + public static function newFromArray( array $values, $maxKeys ) { + $mapCache = new self( $maxKeys ); + $mapCache->cache = ( count( $values ) > $maxKeys ) + ? array_slice( $values, -$maxKeys, null, true ) + : $values; + + return $mapCache; + } + + /** + * @return array Key/value map in order of increasingly recent access + * @since 1.30 + */ + public function toArray() { + return $this->cache; + } + /** * Set a key/value pair. * This will prune the cache if it gets too large based on LRU. * If the item is already set, it will be pushed to the top of the cache. * + * To reduce evictions due to one-off use of many new keys, $rank can be + * set to have keys start at the top of a bottom fraction of the list. A value + * of 3/8 means values start at the top of the bottom 3/8s of the list and are + * moved to the top of the list when accessed a second time. + * * @param string $key * @param mixed $value + * @param float $rank Bottom fraction of the list where keys start off [Default: 1.0] * @return void */ - public function set( $key, $value ) { + public function set( $key, $value, $rank = 1.0 ) { if ( $this->has( $key ) ) { $this->ping( $key ); } elseif ( count( $this->cache ) >= $this->maxCacheKeys ) { @@ -65,7 +94,15 @@ class MapCacheLRU { $evictKey = key( $this->cache ); unset( $this->cache[$evictKey] ); } - $this->cache[$key] = $value; + + if ( $rank < 1.0 && $rank > 0 ) { + $offset = intval( $rank * count( $this->cache ) ); + $this->cache = array_slice( $this->cache, 0, $offset, true ) + + [ $key => $value ] + + array_slice( $this->cache, $offset, null, true ); + } else { + $this->cache[$key] = $value; + } } /** @@ -116,15 +153,16 @@ class MapCacheLRU { * @since 1.28 * @param string $key * @param callable $callback Callback that will produce the value + * @param float $rank Bottom fraction of the list where keys start off [Default: 1.0] * @return mixed The cached value if found or the result of $callback otherwise */ - public function getWithSetCallback( $key, callable $callback ) { + public function getWithSetCallback( $key, callable $callback, $rank = 1.0 ) { if ( $this->has( $key ) ) { $value = $this->get( $key ); } else { $value = call_user_func( $callback ); if ( $value !== false ) { - $this->set( $key, $value ); + $this->set( $key, $value, $rank ); } } diff --git a/tests/phpunit/includes/libs/MapCacheLRUTest.php b/tests/phpunit/includes/libs/MapCacheLRUTest.php new file mode 100644 index 0000000000..60a505721e --- /dev/null +++ b/tests/phpunit/includes/libs/MapCacheLRUTest.php @@ -0,0 +1,114 @@ + 4, 'c' => 3, 'b' => 2, 'a' => 1 ]; + $cache = MapCacheLRU::newFromArray( $raw, 3 ); + + $this->assertSame( true, $cache->has( 'a' ) ); + $this->assertSame( true, $cache->has( 'b' ) ); + $this->assertSame( true, $cache->has( 'c' ) ); + $this->assertSame( 1, $cache->get( 'a' ) ); + $this->assertSame( 2, $cache->get( 'b' ) ); + $this->assertSame( 3, $cache->get( 'c' ) ); + + $this->assertSame( + [ 'a' => 1, 'b' => 2, 'c' => 3 ], + $cache->toArray() + ); + $this->assertSame( + [ 'a', 'b', 'c' ], + $cache->getAllKeys() + ); + + $cache->clear( 'a' ); + $this->assertSame( + [ 'b' => 2, 'c' => 3 ], + $cache->toArray() + ); + + $cache->clear(); + $this->assertSame( + [], + $cache->toArray() + ); + } + + /** + * @covers MapCacheLRU::has() + * @covers MapCacheLRU::get() + * @covers MapCacheLRU::set() + */ + function testLRU() { + $raw = [ 'a' => 1, 'b' => 2, 'c' => 3 ]; + $cache = MapCacheLRU::newFromArray( $raw, 3 ); + + $this->assertSame( true, $cache->has( 'c' ) ); + $this->assertSame( + [ 'a' => 1, 'b' => 2, 'c' => 3 ], + $cache->toArray() + ); + + $this->assertSame( 3, $cache->get( 'c' ) ); + $this->assertSame( + [ 'a' => 1, 'b' => 2, 'c' => 3 ], + $cache->toArray() + ); + + $this->assertSame( 1, $cache->get( 'a' ) ); + $this->assertSame( + [ 'b' => 2, 'c' => 3, 'a' => 1 ], + $cache->toArray() + ); + + $cache->set( 'a', 1 ); + $this->assertSame( + [ 'b' => 2, 'c' => 3, 'a' => 1 ], + $cache->toArray() + ); + + $cache->set( 'b', 22 ); + $this->assertSame( + [ 'c' => 3, 'a' => 1, 'b' => 22 ], + $cache->toArray() + ); + + $cache->set( 'd', 4 ); + $this->assertSame( + [ 'a' => 1, 'b' => 22, 'd' => 4 ], + $cache->toArray() + ); + + $cache->set( 'e', 5, 0.33 ); + $this->assertSame( + [ 'e' => 5, 'b' => 22, 'd' => 4 ], + $cache->toArray() + ); + + $cache->set( 'f', 6, 0.66 ); + $this->assertSame( + [ 'b' => 22, 'f' => 6, 'd' => 4 ], + $cache->toArray() + ); + + $cache->set( 'g', 7, 0.90 ); + $this->assertSame( + [ 'f' => 6, 'g' => 7, 'd' => 4 ], + $cache->toArray() + ); + + $cache->set( 'g', 7, 1.0 ); + $this->assertSame( + [ 'f' => 6, 'd' => 4, 'g' => 7 ], + $cache->toArray() + ); + } +} -- 2.20.1