Hi, Caching is an important technique to trade time (speed of execution) for space (memory consumption) in computation. Used correctly, caching can significantly improve an applicationâs performance. Given the key/value nature of a cache, a Dictionary is often the first data structure used for implementing it. This is however not a good idea since a simple Dictionary is unbounded by definition and can/will lead to explosive cache growth. Quick and dirty hacks to turn a Dictionary into a least-recently-used (LRU) and/or time-to-live (TTL) based limited cache are often incorrect and inefficient. The LRUCache implementation currently in Pharo is too simple and not efficient, being O(n) on its main operation. Pharo deserves and needs a good LRU/TTL cache implementation that can/should be used uniformly in various places of the system and in code built on top of it. That is why I implemented a proposal. Neo-Caching is an implementation of both a good LRU cache as well as a TTL extension of it. The caches are easy to use, yet have a number of interesting features. The implementation is properly O(1) on its main operations and is 2 to 3 times faster than LRUCache. The package also contains a double linked list implementation. The code comes with a full set of unit tests. There are class and method comments and the code is easy to read. The code (which has no dependencies) can be found here http://mc.stfx.eu/Neo http://www.smalltalkhub.com/mc/SvenVanCaekenberghe/Neo/main There is only one package to load. The code has been written in Pharo 3.0 but it should run on older versions as well. Code Letâs create a 16K ordered collection of keys that have some repetitions in them with a reasonable distribution: data := Array streamContents: [ :out | 1 to: 4096 do: [ :each | each primeFactorsOn: out. out nextPut: each ] ]. data := data collect: [ :each | each asWords ]. By using #asWords the keys have better hash properties. Now, we put all this in a cache: cache := NeoLRUCache new. cache maximumWeight: 512. cache factory: [ :key | key ]. data do: [ :each | cache at: each ]. cache. ==> a NeoLRUCache(#512 512/512 [ 1 ] [ :key | key ] 72%) We had a 72% hit ratio, which is good. The cache is of course full, 512/512 with 512 entries (not necessarily the same thing, see further). We can now benchmark this: [ data do: [ :each | cache at: each ] ] bench. ==> '35.8 per second.â And compare it to LRUCache: cache := LRUCache size: 512 factory: [ :key | key ]. [ data do: [ :each | cache at: each ] ] bench. ==> '12.6 per second.â Features Instead of just counting the number of entries, which is the default behaviour, the concept of weight is used to determine when a cache is full. For each cached value, a block or selector is used to compute its weight. When adding a new entry causes the weight to exceed a maximum, eviction of the least recently used item(s) takes place, until the weight is again below the maximum. cache computeWeight: #sizeInMemory; maximumWeight: 16*1024. Will keep the cache below 16Kb in real memory usage. This can be very useful when caching various sized images or MC packages, for example. By default, no concurrent access protection takes place, but optionally a semaphore for mutual exclusion can be used. This slows down access. cache useSemaphore. NeoTTLCache extends NeoLRUCache by maintaining a timestamp for each cached value. Upon cache hit, there is a check to see if this timestamp is not older than the allowed time to live. If so, the value is stale and will be recomputed. (cache := NeoTTLCache new) timeToLive: 10 minutes; factory: [ :key | ZnEasy get: key ]; maximumWeight: 32*1024; computeWeight: #contentLength. cache at: âhttp://zn.stfx.eu/zn/numbers.txt'. ==> a ZnResponse(200 OK text/plain;charset=utf-8 71B) cache ==> a NeoTTLCache(#1 71/32768 #contentLength [ :key | ZnEasy get: key ] 0% 0:00:10:00) Would be a simple HTTP cache, keeping resolved URLs in memory for 10 minutes maximum before refreshing them. It uses #contentLength on ZnResponse to compute the weight. You can see from the print string that there is now 1 entry, while the weight is 17 bytes out of 32768. These are the main points, please have a look at the code. Feedback is welcome. Regards, Sven
Looks useful indeed. Thx. I like the useSemaphore thing. Question: what does Neo stands for as prefix? I wonder. Makes me think of The Matrix and Red Pills. Phil On Tue, Dec 10, 2013 at 4:54 PM, Sven Van Caekenberghe <sven@stfx.eu> wrote:
Hi,
Caching is an important technique to trade time (speed of execution) for space (memory consumption) in computation. Used correctly, caching can significantly improve an applicationâs performance.
Given the key/value nature of a cache, a Dictionary is often the first data structure used for implementing it. This is however not a good idea since a simple Dictionary is unbounded by definition and can/will lead to explosive cache growth.
Quick and dirty hacks to turn a Dictionary into a least-recently-used (LRU) and/or time-to-live (TTL) based limited cache are often incorrect and inefficient.
The LRUCache implementation currently in Pharo is too simple and not efficient, being O(n) on its main operation.
Pharo deserves and needs a good LRU/TTL cache implementation that can/should be used uniformly in various places of the system and in code built on top of it. That is why I implemented a proposal.
Neo-Caching is an implementation of both a good LRU cache as well as a TTL extension of it. The caches are easy to use, yet have a number of interesting features. The implementation is properly O(1) on its main operations and is 2 to 3 times faster than LRUCache. The package also contains a double linked list implementation. The code comes with a full set of unit tests. There are class and method comments and the code is easy to read.
The code (which has no dependencies) can be found here
http://mc.stfx.eu/Neo http://www.smalltalkhub.com/mc/SvenVanCaekenberghe/Neo/main
There is only one package to load. The code has been written in Pharo 3.0 but it should run on older versions as well.
Code
Letâs create a 16K ordered collection of keys that have some repetitions in them with a reasonable distribution:
data := Array streamContents: [ :out | 1 to: 4096 do: [ :each | each primeFactorsOn: out. out nextPut: each ] ]. data := data collect: [ :each | each asWords ].
By using #asWords the keys have better hash properties. Now, we put all this in a cache:
cache := NeoLRUCache new. cache maximumWeight: 512. cache factory: [ :key | key ]. data do: [ :each | cache at: each ]. cache.
==> a NeoLRUCache(#512 512/512 [ 1 ] [ :key | key ] 72%)
We had a 72% hit ratio, which is good. The cache is of course full, 512/512 with 512 entries (not necessarily the same thing, see further).
We can now benchmark this:
[ data do: [ :each | cache at: each ] ] bench.
==> '35.8 per second.â
And compare it to LRUCache:
cache := LRUCache size: 512 factory: [ :key | key ].
[ data do: [ :each | cache at: each ] ] bench.
==> '12.6 per second.â
Features
Instead of just counting the number of entries, which is the default behaviour, the concept of weight is used to determine when a cache is full. For each cached value, a block or selector is used to compute its weight. When adding a new entry causes the weight to exceed a maximum, eviction of the least recently used item(s) takes place, until the weight is again below the maximum.
cache computeWeight: #sizeInMemory; maximumWeight: 16*1024.
Will keep the cache below 16Kb in real memory usage. This can be very useful when caching various sized images or MC packages, for example.
By default, no concurrent access protection takes place, but optionally a semaphore for mutual exclusion can be used. This slows down access.
cache useSemaphore.
NeoTTLCache extends NeoLRUCache by maintaining a timestamp for each cached value. Upon cache hit, there is a check to see if this timestamp is not older than the allowed time to live. If so, the value is stale and will be recomputed.
(cache := NeoTTLCache new) timeToLive: 10 minutes; factory: [ :key | ZnEasy get: key ]; maximumWeight: 32*1024; computeWeight: #contentLength.
cache at: âhttp://zn.stfx.eu/zn/numbers.txt'.
==> a ZnResponse(200 OK text/plain;charset=utf-8 71B)
cache
==> a NeoTTLCache(#1 71/32768 #contentLength [ :key | ZnEasy get: key ] 0% 0:00:10:00)
Would be a simple HTTP cache, keeping resolved URLs in memory for 10 minutes maximum before refreshing them. It uses #contentLength on ZnResponse to compute the weight. You can see from the print string that there is now 1 entry, while the weight is 17 bytes out of 32768.
These are the main points, please have a look at the code. Feedback is welcome.
Regards,
Sven
On 10 Dec 2013, at 17:48, phil@highoctane.be wrote:
Looks useful indeed. Thx.
Thanks.
I like the useSemaphore thing.
If you need it, it is necessary. Otherwise it slows things down.
Question: what does Neo stands for as prefix? I wonder. Makes me think of The Matrix and Red Pills.
Ah, itâs just the name of a namespace, I usually think of it as âNewâ, but yes there is a Matrix link also ;-)
Phil
On Tue, Dec 10, 2013 at 4:54 PM, Sven Van Caekenberghe <sven@stfx.eu> wrote: Hi,
Caching is an important technique to trade time (speed of execution) for space (memory consumption) in computation. Used correctly, caching can significantly improve an applicationâs performance.
Given the key/value nature of a cache, a Dictionary is often the first data structure used for implementing it. This is however not a good idea since a simple Dictionary is unbounded by definition and can/will lead to explosive cache growth.
Quick and dirty hacks to turn a Dictionary into a least-recently-used (LRU) and/or time-to-live (TTL) based limited cache are often incorrect and inefficient.
The LRUCache implementation currently in Pharo is too simple and not efficient, being O(n) on its main operation.
Pharo deserves and needs a good LRU/TTL cache implementation that can/should be used uniformly in various places of the system and in code built on top of it. That is why I implemented a proposal.
Neo-Caching is an implementation of both a good LRU cache as well as a TTL extension of it. The caches are easy to use, yet have a number of interesting features. The implementation is properly O(1) on its main operations and is 2 to 3 times faster than LRUCache. The package also contains a double linked list implementation. The code comes with a full set of unit tests. There are class and method comments and the code is easy to read.
The code (which has no dependencies) can be found here
http://mc.stfx.eu/Neo http://www.smalltalkhub.com/mc/SvenVanCaekenberghe/Neo/main
There is only one package to load. The code has been written in Pharo 3.0 but it should run on older versions as well.
Code
Letâs create a 16K ordered collection of keys that have some repetitions in them with a reasonable distribution:
data := Array streamContents: [ :out | 1 to: 4096 do: [ :each | each primeFactorsOn: out. out nextPut: each ] ]. data := data collect: [ :each | each asWords ].
By using #asWords the keys have better hash properties. Now, we put all this in a cache:
cache := NeoLRUCache new. cache maximumWeight: 512. cache factory: [ :key | key ]. data do: [ :each | cache at: each ]. cache.
==> a NeoLRUCache(#512 512/512 [ 1 ] [ :key | key ] 72%)
We had a 72% hit ratio, which is good. The cache is of course full, 512/512 with 512 entries (not necessarily the same thing, see further).
We can now benchmark this:
[ data do: [ :each | cache at: each ] ] bench.
==> '35.8 per second.â
And compare it to LRUCache:
cache := LRUCache size: 512 factory: [ :key | key ].
[ data do: [ :each | cache at: each ] ] bench.
==> '12.6 per second.â
Features
Instead of just counting the number of entries, which is the default behaviour, the concept of weight is used to determine when a cache is full. For each cached value, a block or selector is used to compute its weight. When adding a new entry causes the weight to exceed a maximum, eviction of the least recently used item(s) takes place, until the weight is again below the maximum.
cache computeWeight: #sizeInMemory; maximumWeight: 16*1024.
Will keep the cache below 16Kb in real memory usage. This can be very useful when caching various sized images or MC packages, for example.
By default, no concurrent access protection takes place, but optionally a semaphore for mutual exclusion can be used. This slows down access.
cache useSemaphore.
NeoTTLCache extends NeoLRUCache by maintaining a timestamp for each cached value. Upon cache hit, there is a check to see if this timestamp is not older than the allowed time to live. If so, the value is stale and will be recomputed.
(cache := NeoTTLCache new) timeToLive: 10 minutes; factory: [ :key | ZnEasy get: key ]; maximumWeight: 32*1024; computeWeight: #contentLength.
cache at: âhttp://zn.stfx.eu/zn/numbers.txt'.
==> a ZnResponse(200 OK text/plain;charset=utf-8 71B)
cache
==> a NeoTTLCache(#1 71/32768 #contentLength [ :key | ZnEasy get: key ] 0% 0:00:10:00)
Would be a simple HTTP cache, keeping resolved URLs in memory for 10 minutes maximum before refreshing them. It uses #contentLength on ZnResponse to compute the weight. You can see from the print string that there is now 1 entry, while the weight is 17 bytes out of 32768.
These are the main points, please have a look at the code. Feedback is welcome.
Regards,
Sven
Thank you Sven! As I always say, I'm a big fan of all your contributions. They certainly close the gap we have with the mainstream solutions. Can I know what do you use it for? 2013/12/10 Sven Van Caekenberghe <sven@stfx.eu>:
On 10 Dec 2013, at 17:48, phil@highoctane.be wrote:
Question: what does Neo stands for as prefix? I wonder. Makes me think of The Matrix and Red Pills. Ah, itâs just the name of a namespace, I usually think of it as âNewâ, but yes there is a Matrix link also ;-)
Because we all know Smalltalk is the red pill... ;-) Esteban A. Maringolo
Sven thanks a lot How can we resist to push this in Pharo 30 :) Stef On Dec 10, 2013, at 4:54 PM, Sven Van Caekenberghe <sven@stfx.eu> wrote:
Hi,
Caching is an important technique to trade time (speed of execution) for space (memory consumption) in computation. Used correctly, caching can significantly improve an applicationâs performance.
Given the key/value nature of a cache, a Dictionary is often the first data structure used for implementing it. This is however not a good idea since a simple Dictionary is unbounded by definition and can/will lead to explosive cache growth.
Quick and dirty hacks to turn a Dictionary into a least-recently-used (LRU) and/or time-to-live (TTL) based limited cache are often incorrect and inefficient.
The LRUCache implementation currently in Pharo is too simple and not efficient, being O(n) on its main operation.
Pharo deserves and needs a good LRU/TTL cache implementation that can/should be used uniformly in various places of the system and in code built on top of it. That is why I implemented a proposal.
Neo-Caching is an implementation of both a good LRU cache as well as a TTL extension of it. The caches are easy to use, yet have a number of interesting features. The implementation is properly O(1) on its main operations and is 2 to 3 times faster than LRUCache. The package also contains a double linked list implementation. The code comes with a full set of unit tests. There are class and method comments and the code is easy to read.
The code (which has no dependencies) can be found here
http://mc.stfx.eu/Neo http://www.smalltalkhub.com/mc/SvenVanCaekenberghe/Neo/main
There is only one package to load. The code has been written in Pharo 3.0 but it should run on older versions as well.
Code
Letâs create a 16K ordered collection of keys that have some repetitions in them with a reasonable distribution:
data := Array streamContents: [ :out | 1 to: 4096 do: [ :each | each primeFactorsOn: out. out nextPut: each ] ]. data := data collect: [ :each | each asWords ].
By using #asWords the keys have better hash properties. Now, we put all this in a cache:
cache := NeoLRUCache new. cache maximumWeight: 512. cache factory: [ :key | key ]. data do: [ :each | cache at: each ]. cache.
==> a NeoLRUCache(#512 512/512 [ 1 ] [ :key | key ] 72%)
We had a 72% hit ratio, which is good. The cache is of course full, 512/512 with 512 entries (not necessarily the same thing, see further).
We can now benchmark this:
[ data do: [ :each | cache at: each ] ] bench.
==> '35.8 per second.â
And compare it to LRUCache:
cache := LRUCache size: 512 factory: [ :key | key ].
[ data do: [ :each | cache at: each ] ] bench.
==> '12.6 per second.â
Features
Instead of just counting the number of entries, which is the default behaviour, the concept of weight is used to determine when a cache is full. For each cached value, a block or selector is used to compute its weight. When adding a new entry causes the weight to exceed a maximum, eviction of the least recently used item(s) takes place, until the weight is again below the maximum.
cache computeWeight: #sizeInMemory; maximumWeight: 16*1024.
Will keep the cache below 16Kb in real memory usage. This can be very useful when caching various sized images or MC packages, for example.
By default, no concurrent access protection takes place, but optionally a semaphore for mutual exclusion can be used. This slows down access.
cache useSemaphore.
NeoTTLCache extends NeoLRUCache by maintaining a timestamp for each cached value. Upon cache hit, there is a check to see if this timestamp is not older than the allowed time to live. If so, the value is stale and will be recomputed.
(cache := NeoTTLCache new) timeToLive: 10 minutes; factory: [ :key | ZnEasy get: key ]; maximumWeight: 32*1024; computeWeight: #contentLength.
cache at: âhttp://zn.stfx.eu/zn/numbers.txt'.
==> a ZnResponse(200 OK text/plain;charset=utf-8 71B)
cache
==> a NeoTTLCache(#1 71/32768 #contentLength [ :key | ZnEasy get: key ] 0% 0:00:10:00)
Would be a simple HTTP cache, keeping resolved URLs in memory for 10 minutes maximum before refreshing them. It uses #contentLength on ZnResponse to compute the weight. You can see from the print string that there is now 1 entry, while the weight is 17 bytes out of 32768.
These are the main points, please have a look at the code. Feedback is welcome.
Regards,
Sven
On 10 Dec 2013, at 23:09, Stéphane Ducasse <stephane.ducasse@inria.fr> wrote:
Sven thanks a lot How can we resist to push this in Pharo 30 :)
That is the idea, and I will do it, but I would first like some feedback/validation.
Stef
On Dec 10, 2013, at 4:54 PM, Sven Van Caekenberghe <sven@stfx.eu> wrote:
Hi,
Caching is an important technique to trade time (speed of execution) for space (memory consumption) in computation. Used correctly, caching can significantly improve an applicationâs performance.
Given the key/value nature of a cache, a Dictionary is often the first data structure used for implementing it. This is however not a good idea since a simple Dictionary is unbounded by definition and can/will lead to explosive cache growth.
Quick and dirty hacks to turn a Dictionary into a least-recently-used (LRU) and/or time-to-live (TTL) based limited cache are often incorrect and inefficient.
The LRUCache implementation currently in Pharo is too simple and not efficient, being O(n) on its main operation.
Pharo deserves and needs a good LRU/TTL cache implementation that can/should be used uniformly in various places of the system and in code built on top of it. That is why I implemented a proposal.
Neo-Caching is an implementation of both a good LRU cache as well as a TTL extension of it. The caches are easy to use, yet have a number of interesting features. The implementation is properly O(1) on its main operations and is 2 to 3 times faster than LRUCache. The package also contains a double linked list implementation. The code comes with a full set of unit tests. There are class and method comments and the code is easy to read.
The code (which has no dependencies) can be found here
http://mc.stfx.eu/Neo http://www.smalltalkhub.com/mc/SvenVanCaekenberghe/Neo/main
There is only one package to load. The code has been written in Pharo 3.0 but it should run on older versions as well.
Code
Letâs create a 16K ordered collection of keys that have some repetitions in them with a reasonable distribution:
data := Array streamContents: [ :out | 1 to: 4096 do: [ :each | each primeFactorsOn: out. out nextPut: each ] ]. data := data collect: [ :each | each asWords ].
By using #asWords the keys have better hash properties. Now, we put all this in a cache:
cache := NeoLRUCache new. cache maximumWeight: 512. cache factory: [ :key | key ]. data do: [ :each | cache at: each ]. cache.
==> a NeoLRUCache(#512 512/512 [ 1 ] [ :key | key ] 72%)
We had a 72% hit ratio, which is good. The cache is of course full, 512/512 with 512 entries (not necessarily the same thing, see further).
We can now benchmark this:
[ data do: [ :each | cache at: each ] ] bench.
==> '35.8 per second.â
And compare it to LRUCache:
cache := LRUCache size: 512 factory: [ :key | key ].
[ data do: [ :each | cache at: each ] ] bench.
==> '12.6 per second.â
Features
Instead of just counting the number of entries, which is the default behaviour, the concept of weight is used to determine when a cache is full. For each cached value, a block or selector is used to compute its weight. When adding a new entry causes the weight to exceed a maximum, eviction of the least recently used item(s) takes place, until the weight is again below the maximum.
cache computeWeight: #sizeInMemory; maximumWeight: 16*1024.
Will keep the cache below 16Kb in real memory usage. This can be very useful when caching various sized images or MC packages, for example.
By default, no concurrent access protection takes place, but optionally a semaphore for mutual exclusion can be used. This slows down access.
cache useSemaphore.
NeoTTLCache extends NeoLRUCache by maintaining a timestamp for each cached value. Upon cache hit, there is a check to see if this timestamp is not older than the allowed time to live. If so, the value is stale and will be recomputed.
(cache := NeoTTLCache new) timeToLive: 10 minutes; factory: [ :key | ZnEasy get: key ]; maximumWeight: 32*1024; computeWeight: #contentLength.
cache at: âhttp://zn.stfx.eu/zn/numbers.txt'.
==> a ZnResponse(200 OK text/plain;charset=utf-8 71B)
cache
==> a NeoTTLCache(#1 71/32768 #contentLength [ :key | ZnEasy get: key ] 0% 0:00:10:00)
Would be a simple HTTP cache, keeping resolved URLs in memory for 10 minutes maximum before refreshing them. It uses #contentLength on ZnResponse to compute the weight. You can see from the print string that there is now 1 entry, while the weight is 17 bytes out of 32768.
These are the main points, please have a look at the code. Feedback is welcome.
Regards,
Sven
Great! I took a look at the code. It's simple and clean. Thanks a lot for this addition. It is highly needed. Cheers, Doru On Tue, Dec 10, 2013 at 11:58 PM, Sven Van Caekenberghe <sven@stfx.eu>wrote:
On 10 Dec 2013, at 23:09, Stéphane Ducasse <stephane.ducasse@inria.fr> wrote:
Sven thanks a lot How can we resist to push this in Pharo 30 :)
That is the idea, and I will do it, but I would first like some feedback/validation.
Stef
On Dec 10, 2013, at 4:54 PM, Sven Van Caekenberghe <sven@stfx.eu> wrote:
Hi,
Caching is an important technique to trade time (speed of execution) for space (memory consumption) in computation. Used correctly, caching can significantly improve an applicationâs performance.
Given the key/value nature of a cache, a Dictionary is often the first data structure used for implementing it. This is however not a good idea since a simple Dictionary is unbounded by definition and can/will lead to explosive cache growth.
Quick and dirty hacks to turn a Dictionary into a least-recently-used (LRU) and/or time-to-live (TTL) based limited cache are often incorrect and inefficient.
The LRUCache implementation currently in Pharo is too simple and not efficient, being O(n) on its main operation.
Pharo deserves and needs a good LRU/TTL cache implementation that can/should be used uniformly in various places of the system and in code built on top of it. That is why I implemented a proposal.
Neo-Caching is an implementation of both a good LRU cache as well as a TTL extension of it. The caches are easy to use, yet have a number of interesting features. The implementation is properly O(1) on its main operations and is 2 to 3 times faster than LRUCache. The package also contains a double linked list implementation. The code comes with a full set of unit tests. There are class and method comments and the code is easy to read.
The code (which has no dependencies) can be found here
http://mc.stfx.eu/Neo http://www.smalltalkhub.com/mc/SvenVanCaekenberghe/Neo/main
There is only one package to load. The code has been written in Pharo 3.0 but it should run on older versions as well.
Code
Letâs create a 16K ordered collection of keys that have some repetitions in them with a reasonable distribution:
data := Array streamContents: [ :out | 1 to: 4096 do: [ :each | each primeFactorsOn: out. out nextPut: each ] ]. data := data collect: [ :each | each asWords ].
By using #asWords the keys have better hash properties. Now, we put all this in a cache:
cache := NeoLRUCache new. cache maximumWeight: 512. cache factory: [ :key | key ]. data do: [ :each | cache at: each ]. cache.
==> a NeoLRUCache(#512 512/512 [ 1 ] [ :key | key ] 72%)
We had a 72% hit ratio, which is good. The cache is of course full, 512/512 with 512 entries (not necessarily the same thing, see further).
We can now benchmark this:
[ data do: [ :each | cache at: each ] ] bench.
==> '35.8 per second.â
And compare it to LRUCache:
cache := LRUCache size: 512 factory: [ :key | key ].
[ data do: [ :each | cache at: each ] ] bench.
==> '12.6 per second.â
Features
Instead of just counting the number of entries, which is the default behaviour, the concept of weight is used to determine when a cache is full. For each cached value, a block or selector is used to compute its weight. When adding a new entry causes the weight to exceed a maximum, eviction of the least recently used item(s) takes place, until the weight is again below the maximum.
cache computeWeight: #sizeInMemory; maximumWeight: 16*1024.
Will keep the cache below 16Kb in real memory usage. This can be very useful when caching various sized images or MC packages, for example.
By default, no concurrent access protection takes place, but optionally a semaphore for mutual exclusion can be used. This slows down access.
cache useSemaphore.
NeoTTLCache extends NeoLRUCache by maintaining a timestamp for each cached value. Upon cache hit, there is a check to see if this timestamp is not older than the allowed time to live. If so, the value is stale and will be recomputed.
(cache := NeoTTLCache new) timeToLive: 10 minutes; factory: [ :key | ZnEasy get: key ]; maximumWeight: 32*1024; computeWeight: #contentLength.
cache at: âhttp://zn.stfx.eu/zn/numbers.txt'.
==> a ZnResponse(200 OK text/plain;charset=utf-8 71B)
cache
==> a NeoTTLCache(#1 71/32768 #contentLength [ :key | ZnEasy get: key ] 0% 0:00:10:00)
Would be a simple HTTP cache, keeping resolved URLs in memory for 10 minutes maximum before refreshing them. It uses #contentLength on ZnResponse to compute the weight. You can see from the print string that there is now 1 entry, while the weight is 17 bytes out of 32768.
These are the main points, please have a look at the code. Feedback is welcome.
Regards,
Sven
-- www.tudorgirba.com "Every thing has its own flow"
This is awesome! Thanks Sven :) Nico Sven Van Caekenberghe writes:
On 10 Dec 2013, at 23:09, Stéphane Ducasse <stephane.ducasse@inria.fr> wrote:
Sven thanks a lot How can we resist to push this in Pharo 30 :)
That is the idea, and I will do it, but I would first like some feedback/validation.
Stef
On Dec 10, 2013, at 4:54 PM, Sven Van Caekenberghe <sven@stfx.eu> wrote:
Hi,
Caching is an important technique to trade time (speed of execution) for space (memory consumption) in computation. Used correctly, caching can significantly improve an applicationâs performance.
Given the key/value nature of a cache, a Dictionary is often the first data structure used for implementing it. This is however not a good idea since a simple Dictionary is unbounded by definition and can/will lead to explosive cache growth.
Quick and dirty hacks to turn a Dictionary into a least-recently-used (LRU) and/or time-to-live (TTL) based limited cache are often incorrect and inefficient.
The LRUCache implementation currently in Pharo is too simple and not efficient, being O(n) on its main operation.
Pharo deserves and needs a good LRU/TTL cache implementation that can/should be used uniformly in various places of the system and in code built on top of it. That is why I implemented a proposal.
Neo-Caching is an implementation of both a good LRU cache as well as a TTL extension of it. The caches are easy to use, yet have a number of interesting features. The implementation is properly O(1) on its main operations and is 2 to 3 times faster than LRUCache. The package also contains a double linked list implementation. The code comes with a full set of unit tests. There are class and method comments and the code is easy to read.
The code (which has no dependencies) can be found here
http://mc.stfx.eu/Neo http://www.smalltalkhub.com/mc/SvenVanCaekenberghe/Neo/main
There is only one package to load. The code has been written in Pharo 3.0 but it should run on older versions as well.
Code
Letâs create a 16K ordered collection of keys that have some repetitions in them with a reasonable distribution:
data := Array streamContents: [ :out | 1 to: 4096 do: [ :each | each primeFactorsOn: out. out nextPut: each ] ]. data := data collect: [ :each | each asWords ].
By using #asWords the keys have better hash properties. Now, we put all this in a cache:
cache := NeoLRUCache new. cache maximumWeight: 512. cache factory: [ :key | key ]. data do: [ :each | cache at: each ]. cache.
==> a NeoLRUCache(#512 512/512 [ 1 ] [ :key | key ] 72%)
We had a 72% hit ratio, which is good. The cache is of course full, 512/512 with 512 entries (not necessarily the same thing, see further).
We can now benchmark this:
[ data do: [ :each | cache at: each ] ] bench.
==> '35.8 per second.â
And compare it to LRUCache:
cache := LRUCache size: 512 factory: [ :key | key ].
[ data do: [ :each | cache at: each ] ] bench.
==> '12.6 per second.â
Features
Instead of just counting the number of entries, which is the default behaviour, the concept of weight is used to determine when a cache is full. For each cached value, a block or selector is used to compute its weight. When adding a new entry causes the weight to exceed a maximum, eviction of the least recently used item(s) takes place, until the weight is again below the maximum.
cache computeWeight: #sizeInMemory; maximumWeight: 16*1024.
Will keep the cache below 16Kb in real memory usage. This can be very useful when caching various sized images or MC packages, for example.
By default, no concurrent access protection takes place, but optionally a semaphore for mutual exclusion can be used. This slows down access.
cache useSemaphore.
NeoTTLCache extends NeoLRUCache by maintaining a timestamp for each cached value. Upon cache hit, there is a check to see if this timestamp is not older than the allowed time to live. If so, the value is stale and will be recomputed.
(cache := NeoTTLCache new) timeToLive: 10 minutes; factory: [ :key | ZnEasy get: key ]; maximumWeight: 32*1024; computeWeight: #contentLength.
cache at: âhttp://zn.stfx.eu/zn/numbers.txt'.
==> a ZnResponse(200 OK text/plain;charset=utf-8 71B)
cache
==> a NeoTTLCache(#1 71/32768 #contentLength [ :key | ZnEasy get: key ] 0% 0:00:10:00)
Would be a simple HTTP cache, keeping resolved URLs in memory for 10 minutes maximum before refreshing them. It uses #contentLength on ZnResponse to compute the weight. You can see from the print string that there is now 1 entry, while the weight is 17 bytes out of 32768.
These are the main points, please have a look at the code. Feedback is welcome.
Regards,
Sven
-- Nicolas Petton http://nicolas-petton.fr
On Tue, Dec 10, 2013 at 11:09 PM, Stéphane Ducasse < stephane.ducasse@inria.fr> wrote:
Sven thanks a lot
yes! really cool!
How can we resist to push this in Pharo 30 :)
over my dead body :) but in Pharo 4...
Stef
On Dec 10, 2013, at 4:54 PM, Sven Van Caekenberghe <sven@stfx.eu> wrote:
Hi,
Caching is an important technique to trade time (speed of execution) for space (memory consumption) in computation. Used correctly, caching can significantly improve an applicationâs performance.
Given the key/value nature of a cache, a Dictionary is often the first data structure used for implementing it. This is however not a good idea since a simple Dictionary is unbounded by definition and can/will lead to explosive cache growth.
Quick and dirty hacks to turn a Dictionary into a least-recently-used (LRU) and/or time-to-live (TTL) based limited cache are often incorrect and inefficient.
The LRUCache implementation currently in Pharo is too simple and not efficient, being O(n) on its main operation.
Pharo deserves and needs a good LRU/TTL cache implementation that can/should be used uniformly in various places of the system and in code built on top of it. That is why I implemented a proposal.
Neo-Caching is an implementation of both a good LRU cache as well as a TTL extension of it. The caches are easy to use, yet have a number of interesting features. The implementation is properly O(1) on its main operations and is 2 to 3 times faster than LRUCache. The package also contains a double linked list implementation. The code comes with a full set of unit tests. There are class and method comments and the code is easy to read.
The code (which has no dependencies) can be found here
http://mc.stfx.eu/Neo http://www.smalltalkhub.com/mc/SvenVanCaekenberghe/Neo/main
There is only one package to load. The code has been written in Pharo 3.0 but it should run on older versions as well.
Code
Letâs create a 16K ordered collection of keys that have some repetitions in them with a reasonable distribution:
data := Array streamContents: [ :out | 1 to: 4096 do: [ :each | each primeFactorsOn: out. out nextPut: each ] ]. data := data collect: [ :each | each asWords ].
By using #asWords the keys have better hash properties. Now, we put all this in a cache:
cache := NeoLRUCache new. cache maximumWeight: 512. cache factory: [ :key | key ]. data do: [ :each | cache at: each ]. cache.
==> a NeoLRUCache(#512 512/512 [ 1 ] [ :key | key ] 72%)
We had a 72% hit ratio, which is good. The cache is of course full, 512/512 with 512 entries (not necessarily the same thing, see further).
We can now benchmark this:
[ data do: [ :each | cache at: each ] ] bench.
==> '35.8 per second.â
And compare it to LRUCache:
cache := LRUCache size: 512 factory: [ :key | key ].
[ data do: [ :each | cache at: each ] ] bench.
==> '12.6 per second.â
Features
Instead of just counting the number of entries, which is the default behaviour, the concept of weight is used to determine when a cache is full. For each cached value, a block or selector is used to compute its weight. When adding a new entry causes the weight to exceed a maximum, eviction of the least recently used item(s) takes place, until the weight is again below the maximum.
cache computeWeight: #sizeInMemory; maximumWeight: 16*1024.
Will keep the cache below 16Kb in real memory usage. This can be very useful when caching various sized images or MC packages, for example.
By default, no concurrent access protection takes place, but optionally a semaphore for mutual exclusion can be used. This slows down access.
cache useSemaphore.
NeoTTLCache extends NeoLRUCache by maintaining a timestamp for each cached value. Upon cache hit, there is a check to see if this timestamp is not older than the allowed time to live. If so, the value is stale and will be recomputed.
(cache := NeoTTLCache new) timeToLive: 10 minutes; factory: [ :key | ZnEasy get: key ]; maximumWeight: 32*1024; computeWeight: #contentLength.
cache at: âhttp://zn.stfx.eu/zn/numbers.txt'.
==> a ZnResponse(200 OK text/plain;charset=utf-8 71B)
cache
==> a NeoTTLCache(#1 71/32768 #contentLength [ :key | ZnEasy get: key ] 0% 0:00:10:00)
Would be a simple HTTP cache, keeping resolved URLs in memory for 10 minutes maximum before refreshing them. It uses #contentLength on ZnResponse to compute the weight. You can see from the print string that there is now 1 entry, while the weight is 17 bytes out of 32768.
These are the main points, please have a look at the code. Feedback is welcome.
Regards,
Sven
On Dec 11, 2013, at 12:29 PM, Esteban Lorenzano <estebanlm@gmail.com> wrote:
On Tue, Dec 10, 2013 at 11:09 PM, Stéphane Ducasse <stephane.ducasse@inria.fr> wrote: Sven thanks a lot
yes! really cool!
How can we resist to push this in Pharo 30 :)
over my dead body :) but in Pharo 4â¦
you are saying that you will let squeak be in advance compared to Pharo :) I cannot believe that :). Stef
Stef
On Dec 10, 2013, at 4:54 PM, Sven Van Caekenberghe <sven@stfx.eu> wrote:
Hi,
Caching is an important technique to trade time (speed of execution) for space (memory consumption) in computation. Used correctly, caching can significantly improve an applicationâs performance.
Given the key/value nature of a cache, a Dictionary is often the first data structure used for implementing it. This is however not a good idea since a simple Dictionary is unbounded by definition and can/will lead to explosive cache growth.
Quick and dirty hacks to turn a Dictionary into a least-recently-used (LRU) and/or time-to-live (TTL) based limited cache are often incorrect and inefficient.
The LRUCache implementation currently in Pharo is too simple and not efficient, being O(n) on its main operation.
Pharo deserves and needs a good LRU/TTL cache implementation that can/should be used uniformly in various places of the system and in code built on top of it. That is why I implemented a proposal.
Neo-Caching is an implementation of both a good LRU cache as well as a TTL extension of it. The caches are easy to use, yet have a number of interesting features. The implementation is properly O(1) on its main operations and is 2 to 3 times faster than LRUCache. The package also contains a double linked list implementation. The code comes with a full set of unit tests. There are class and method comments and the code is easy to read.
The code (which has no dependencies) can be found here
http://mc.stfx.eu/Neo http://www.smalltalkhub.com/mc/SvenVanCaekenberghe/Neo/main
There is only one package to load. The code has been written in Pharo 3.0 but it should run on older versions as well.
Code
Letâs create a 16K ordered collection of keys that have some repetitions in them with a reasonable distribution:
data := Array streamContents: [ :out | 1 to: 4096 do: [ :each | each primeFactorsOn: out. out nextPut: each ] ]. data := data collect: [ :each | each asWords ].
By using #asWords the keys have better hash properties. Now, we put all this in a cache:
cache := NeoLRUCache new. cache maximumWeight: 512. cache factory: [ :key | key ]. data do: [ :each | cache at: each ]. cache.
==> a NeoLRUCache(#512 512/512 [ 1 ] [ :key | key ] 72%)
We had a 72% hit ratio, which is good. The cache is of course full, 512/512 with 512 entries (not necessarily the same thing, see further).
We can now benchmark this:
[ data do: [ :each | cache at: each ] ] bench.
==> '35.8 per second.â
And compare it to LRUCache:
cache := LRUCache size: 512 factory: [ :key | key ].
[ data do: [ :each | cache at: each ] ] bench.
==> '12.6 per second.â
Features
Instead of just counting the number of entries, which is the default behaviour, the concept of weight is used to determine when a cache is full. For each cached value, a block or selector is used to compute its weight. When adding a new entry causes the weight to exceed a maximum, eviction of the least recently used item(s) takes place, until the weight is again below the maximum.
cache computeWeight: #sizeInMemory; maximumWeight: 16*1024.
Will keep the cache below 16Kb in real memory usage. This can be very useful when caching various sized images or MC packages, for example.
By default, no concurrent access protection takes place, but optionally a semaphore for mutual exclusion can be used. This slows down access.
cache useSemaphore.
NeoTTLCache extends NeoLRUCache by maintaining a timestamp for each cached value. Upon cache hit, there is a check to see if this timestamp is not older than the allowed time to live. If so, the value is stale and will be recomputed.
(cache := NeoTTLCache new) timeToLive: 10 minutes; factory: [ :key | ZnEasy get: key ]; maximumWeight: 32*1024; computeWeight: #contentLength.
cache at: âhttp://zn.stfx.eu/zn/numbers.txt'.
==> a ZnResponse(200 OK text/plain;charset=utf-8 71B)
cache
==> a NeoTTLCache(#1 71/32768 #contentLength [ :key | ZnEasy get: key ] 0% 0:00:10:00)
Would be a simple HTTP cache, keeping resolved URLs in memory for 10 minutes maximum before refreshing them. It uses #contentLength on ZnResponse to compute the weight. You can see from the print string that there is now 1 entry, while the weight is 17 bytes out of 32768.
These are the main points, please have a look at the code. Feedback is welcome.
Regards,
Sven
On 11 Dec 2013, at 12:48, Stéphane Ducasse <stephane.ducasse@inria.fr> wrote:
On Dec 11, 2013, at 12:29 PM, Esteban Lorenzano <estebanlm@gmail.com> wrote:
On Tue, Dec 10, 2013 at 11:09 PM, Stéphane Ducasse <stephane.ducasse@inria.fr> wrote: Sven thanks a lot
yes! really cool!
How can we resist to push this in Pharo 30 :)
over my dead body :) but in Pharo 4â¦
you are saying that you will let squeak be in advance compared to Pharo :) I cannot believe that :).
In any case: https://pharo.fogbugz.com/f/cases/12398/Update-LRUCache-Implementation There are currently only 3 LRUCache users, the risk is minimal, I think. BTW, the reason I started this is because I want better caching for Monticello stuff. You know, the multiple MBâs being used/waisted when you work for a couple of days in the same image, the result of boundless caching using stupid dictionaries. But I am waiting for this reckless young Swiss guy coming back after his thesis is written ;-)
Stef
Stef
On Dec 10, 2013, at 4:54 PM, Sven Van Caekenberghe <sven@stfx.eu> wrote:
Hi,
Caching is an important technique to trade time (speed of execution) for space (memory consumption) in computation. Used correctly, caching can significantly improve an applicationâs performance.
Given the key/value nature of a cache, a Dictionary is often the first data structure used for implementing it. This is however not a good idea since a simple Dictionary is unbounded by definition and can/will lead to explosive cache growth.
Quick and dirty hacks to turn a Dictionary into a least-recently-used (LRU) and/or time-to-live (TTL) based limited cache are often incorrect and inefficient.
The LRUCache implementation currently in Pharo is too simple and not efficient, being O(n) on its main operation.
Pharo deserves and needs a good LRU/TTL cache implementation that can/should be used uniformly in various places of the system and in code built on top of it. That is why I implemented a proposal.
Neo-Caching is an implementation of both a good LRU cache as well as a TTL extension of it. The caches are easy to use, yet have a number of interesting features. The implementation is properly O(1) on its main operations and is 2 to 3 times faster than LRUCache. The package also contains a double linked list implementation. The code comes with a full set of unit tests. There are class and method comments and the code is easy to read.
The code (which has no dependencies) can be found here
http://mc.stfx.eu/Neo http://www.smalltalkhub.com/mc/SvenVanCaekenberghe/Neo/main
There is only one package to load. The code has been written in Pharo 3.0 but it should run on older versions as well.
Code
Letâs create a 16K ordered collection of keys that have some repetitions in them with a reasonable distribution:
data := Array streamContents: [ :out | 1 to: 4096 do: [ :each | each primeFactorsOn: out. out nextPut: each ] ]. data := data collect: [ :each | each asWords ].
By using #asWords the keys have better hash properties. Now, we put all this in a cache:
cache := NeoLRUCache new. cache maximumWeight: 512. cache factory: [ :key | key ]. data do: [ :each | cache at: each ]. cache.
==> a NeoLRUCache(#512 512/512 [ 1 ] [ :key | key ] 72%)
We had a 72% hit ratio, which is good. The cache is of course full, 512/512 with 512 entries (not necessarily the same thing, see further).
We can now benchmark this:
[ data do: [ :each | cache at: each ] ] bench.
==> '35.8 per second.â
And compare it to LRUCache:
cache := LRUCache size: 512 factory: [ :key | key ].
[ data do: [ :each | cache at: each ] ] bench.
==> '12.6 per second.â
Features
Instead of just counting the number of entries, which is the default behaviour, the concept of weight is used to determine when a cache is full. For each cached value, a block or selector is used to compute its weight. When adding a new entry causes the weight to exceed a maximum, eviction of the least recently used item(s) takes place, until the weight is again below the maximum.
cache computeWeight: #sizeInMemory; maximumWeight: 16*1024.
Will keep the cache below 16Kb in real memory usage. This can be very useful when caching various sized images or MC packages, for example.
By default, no concurrent access protection takes place, but optionally a semaphore for mutual exclusion can be used. This slows down access.
cache useSemaphore.
NeoTTLCache extends NeoLRUCache by maintaining a timestamp for each cached value. Upon cache hit, there is a check to see if this timestamp is not older than the allowed time to live. If so, the value is stale and will be recomputed.
(cache := NeoTTLCache new) timeToLive: 10 minutes; factory: [ :key | ZnEasy get: key ]; maximumWeight: 32*1024; computeWeight: #contentLength.
cache at: âhttp://zn.stfx.eu/zn/numbers.txt'.
==> a ZnResponse(200 OK text/plain;charset=utf-8 71B)
cache
==> a NeoTTLCache(#1 71/32768 #contentLength [ :key | ZnEasy get: key ] 0% 0:00:10:00)
Would be a simple HTTP cache, keeping resolved URLs in memory for 10 minutes maximum before refreshing them. It uses #contentLength on ZnResponse to compute the weight. You can see from the print string that there is now 1 entry, while the weight is 17 bytes out of 32768.
These are the main points, please have a look at the code. Feedback is welcome.
Regards,
Sven
Hi,
By default, no concurrent access protection takes place, but optionally a semaphore for mutual exclusion can be used. This slows down access.
cache useSemaphore.
There was enough "awesomes" already :-) so now some critics :-) Wouldn't it be better to rename #useSemaphore to #beThreadSafe or #beSynchronized. Also I would use recursion lock (monitor, if you like) rather than plain mutex. Best, Jan
Hi Jan, On 11 Dec 2013, at 12:49, Jan Vrany <jan.vrany@fit.cvut.cz> wrote:
Hi,
By default, no concurrent access protection takes place, but optionally a semaphore for mutual exclusion can be used. This slows down access.
cache useSemaphore.
There was enough "awesomes" already :-) so now some critics :-)
I like constructive feedback !
Wouldn't it be better to rename #useSemaphore to #beThreadSafe or #beSynchronized.
Yes, specifying the goal/result is better than specifying the means. I think I will go for #beThreadSafe (although threads in Pharo are called Processes ;-). The last one reminds me of Java and we donât have a âsynchronisedâ concept in Pharo AFAIK.
Also I would use recursion lock (monitor, if you like) rather than plain mutex.
Iâve used both, they both work. But I must admit that in my mind the difference is not very clear. A monitor can be re-entered while a semaphore cannot, but I doubt this is necessary here. Any other reasons to choose one over the other ? Speed ? Sven
Best, Jan
On 11/12/13 12:20, Sven Van Caekenberghe wrote:
Hi Jan,
On 11 Dec 2013, at 12:49, Jan Vrany <jan.vrany@fit.cvut.cz> wrote:
Hi,
By default, no concurrent access protection takes place, but optionally a semaphore for mutual exclusion can be used. This slows down access.
cache useSemaphore.
There was enough "awesomes" already :-) so now some critics :-)
I like constructive feedback !
Wouldn't it be better to rename #useSemaphore to #beThreadSafe or #beSynchronized.
Yes, specifying the goal/result is better than specifying the means. I think I will go for #beThreadSafe (although threads in Pharo are called Processes ;-). The last one reminds me of Java and we donât have a âsynchronisedâ concept in Pharo AFAIK.
Also I would use recursion lock (monitor, if you like) rather than plain mutex.
Iâve used both, they both work. But I must admit that in my mind the difference is not very clear. A monitor can be re-entered while a semaphore cannot,
That's exactly the difference, subtle but important :-) but I doubt this is necessary here. Imagine you need Fibonacci number and want to cache them for speed. How would one do that? Obvious solution would be: fibCache := NeoCache ... fibCache factory: [:key | (fibCache at: key - 1) + (fibCache at: key - 1) ]. If I understood the code correctly `fibCache at: 10` would hang, right?
Any other reasons to choose one over the other ? Speed ?
Speed-wise, it depends on implementation. The cost of recursion lock could be reduced to couple machine instructions in case there's no contention (which is usually the case). Actually, this would make an interesting use-case for NB...
Sven
Best, Jan
On 11 Dec 2013, at 13:42, Jan Vrany <jan.vrany@fit.cvut.cz> wrote:
On 11/12/13 12:20, Sven Van Caekenberghe wrote:
Hi Jan,
On 11 Dec 2013, at 12:49, Jan Vrany <jan.vrany@fit.cvut.cz> wrote:
Hi,
By default, no concurrent access protection takes place, but optionally a semaphore for mutual exclusion can be used. This slows down access.
cache useSemaphore.
There was enough "awesomes" already :-) so now some critics :-)
I like constructive feedback !
Wouldn't it be better to rename #useSemaphore to #beThreadSafe or #beSynchronized.
Yes, specifying the goal/result is better than specifying the means. I think I will go for #beThreadSafe (although threads in Pharo are called Processes ;-). The last one reminds me of Java and we donât have a âsynchronisedâ concept in Pharo AFAIK.
Also I would use recursion lock (monitor, if you like) rather than plain mutex.
Iâve used both, they both work. But I must admit that in my mind the difference is not very clear. A monitor can be re-entered while a semaphore cannot,
That's exactly the difference, subtle but important :-)
but I doubt this is necessary here.
Imagine you need Fibonacci number and want to cache them for speed. How would one do that? Obvious solution would be:
fibCache := NeoCache ... fibCache factory: [:key | (fibCache at: key - 1) + (fibCache at: key - 1) ].
If I understood the code correctly `fibCache at: 10` would hang, right?
OK, you convinced me ! Thanks for the explanation. I will even make the fib example part of the unit tests. But I will probably change it to [ :key | key < 2 ifTrue: [ key ] ifFalse: [ (fibCache at: key - 1) + (fibCache at: key - 1) ] ] ;-)
Any other reasons to choose one over the other ? Speed ?
Speed-wise, it depends on implementation. The cost of recursion lock could be reduced to couple machine instructions in case there's no contention (which is usually the case).
Iâll measure it.
Actually, this would make an interesting use-case for NB...
Sven
Best, Jan
On 11 Dec 2013, at 14:03, Sven Van Caekenberghe <sven@stfx.eu> wrote:
On 11 Dec 2013, at 13:42, Jan Vrany <jan.vrany@fit.cvut.cz> wrote:
On 11/12/13 12:20, Sven Van Caekenberghe wrote:
Hi Jan,
On 11 Dec 2013, at 12:49, Jan Vrany <jan.vrany@fit.cvut.cz> wrote:
Hi,
By default, no concurrent access protection takes place, but optionally a semaphore for mutual exclusion can be used. This slows down access.
cache useSemaphore.
There was enough "awesomes" already :-) so now some critics :-)
I like constructive feedback !
Wouldn't it be better to rename #useSemaphore to #beThreadSafe or #beSynchronized.
Yes, specifying the goal/result is better than specifying the means. I think I will go for #beThreadSafe (although threads in Pharo are called Processes ;-). The last one reminds me of Java and we donât have a âsynchronisedâ concept in Pharo AFAIK.
Also I would use recursion lock (monitor, if you like) rather than plain mutex.
Iâve used both, they both work. But I must admit that in my mind the difference is not very clear. A monitor can be re-entered while a semaphore cannot,
That's exactly the difference, subtle but important :-)
but I doubt this is necessary here.
Imagine you need Fibonacci number and want to cache them for speed. How would one do that? Obvious solution would be:
fibCache := NeoCache ... fibCache factory: [:key | (fibCache at: key - 1) + (fibCache at: key - 1) ].
If I understood the code correctly `fibCache at: 10` would hang, right?
OK, you convinced me ! Thanks for the explanation.
I will even make the fib example part of the unit tests.
=== Name: Neo-Caching-SvenVanCaekenberghe.15 Author: SvenVanCaekenberghe Time: 11 December 2013, 5:07:11.601995 pm UUID: 35273b73-8caf-4810-afc5-614d7c690580 Ancestors: Neo-Caching-SvenVanCaekenberghe.14 processed some feedback by Jan Vrany (Thx!): - renamed #useSemaphore to #beThreadSafe - use a Monitor instead of a Semaphore for mutual exclusion so that it can be re-entered safely - added #testFibonacci - added some clarifications to NeoTTLCache's class comment ===
But I will probably change it to
[ :key | key < 2 ifTrue: [ key ] ifFalse: [ (fibCache at: key - 1) + (fibCache at: key - 1) ] ]
;-)
Any other reasons to choose one over the other ? Speed ?
Speed-wise, it depends on implementation. The cost of recursion lock could be reduced to couple machine instructions in case there's no contention (which is usually the case).
Iâll measure it.
Actually, this would make an interesting use-case for NB...
Sven
Best, Jan
participants (8)
-
Esteban A. Maringolo -
Esteban Lorenzano -
Jan Vrany -
Nicolas Petton -
phil＠highoctane.be -
Stéphane Ducasse -
Sven Van Caekenberghe -
Tudor Girba