[ANN] LRUDictionary

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|

[ANN] LRUDictionary

NorbertHartl
I like to announce a tiny utility I did for my last project. It is only a single class that basically works like LRUCache internally but on the outside it is more like a dictionary. And it has no factory block.

If you don't know LRUCache, it's a fixed size dictionary that sorts its elements by usage in a "Least Recently Used" fashion. Meaning the last used element is put in front and the least used at the end. Elements get discarded at the end if space is full.

Apart from #at: that is provided by LRUCache , LRUDictionary implements to following methods

at:ifAbsent:
at:ifAbsentPut:
at:ifPresent:
at:put:
removeAt:
removeKey:
removeKey:ifAbsent

It is available here

MCHttpRepository
        location: 'http://source.selfish.org/mc/misc'
        user: ''
        password: ''

Blog article is here

http://norbert.hartl.name/blog/lrudictionary/

hope you like it,

Norbert
Reply | Threaded
Open this post in threaded view
|

Re: [Pharo-project] [ANN] LRUDictionary

NorbertHartl
I always forget to move stuff. I moved it to squeaksource

http://ss3.gemstone.com/ss/lrudictionary.html

Norbert

Am 11.05.2012 um 14:51 schrieb Norbert Hartl:

> I like to announce a tiny utility I did for my last project. It is only a single class that basically works like LRUCache internally but on the outside it is more like a dictionary. And it has no factory block.
>
> If you don't know LRUCache, it's a fixed size dictionary that sorts its elements by usage in a "Least Recently Used" fashion. Meaning the last used element is put in front and the least used at the end. Elements get discarded at the end if space is full.
>
> Apart from #at: that is provided by LRUCache , LRUDictionary implements to following methods
>
> at:ifAbsent:
> at:ifAbsentPut:
> at:ifPresent:
> at:put:
> removeAt:
> removeKey:
> removeKey:ifAbsent
>
> It is available here
>
> MCHttpRepository
> location: 'http://source.selfish.org/mc/misc'
> user: ''
> password: ''
>
> Blog article is here
>
> http://norbert.hartl.name/blog/lrudictionary/
>
> hope you like it,
>
> Norbert


Reply | Threaded
Open this post in threaded view
|

Re: [ANN] LRUDictionary

Sven Van Caekenberghe
In reply to this post by NorbertHartl
Hi Norbert,

On 11 May 2012, at 14:51, Norbert Hartl wrote:

> I like to announce a tiny utility I did for my last project. It is only a single class that basically works like LRUCache internally but on the outside it is more like a dictionary. And it has no factory block.
>
> If you don't know LRUCache, it's a fixed size dictionary that sorts its elements by usage in a "Least Recently Used" fashion. Meaning the last used element is put in front and the least used at the end. Elements get discarded at the end if space is full.
>
> Apart from #at: that is provided by LRUCache , LRUDictionary implements to following methods
>
> at:ifAbsent:
> at:ifAbsentPut:
> at:ifPresent:
> at:put:
> removeAt:
> removeKey:
> removeKey:ifAbsent
>
> It is available here
>
> MCHttpRepository
> location: 'http://source.selfish.org/mc/misc'
> user: ''
> password: ''
>
> Blog article is here
>
> http://norbert.hartl.name/blog/lrudictionary/
>
> hope you like it,
>
> Norbert

This code strikes me as less than optimal:

putInFront: anObject fromIndex: aNumber
        values
                replaceFrom: 2
                to: aNumber
                with: (values first: aNumber - 1).
        values at: 1 put: anObject.
        ^ anObject

#first: does a copy no ?

#replaceFrom:to:with:startingAt: can do in place shifting, if you are careful.
I would also optimize for the case when the object is already in front.

But even then, all this shifting on each #at: access is a bit costly for a cache, no ?
The alternative, working with timestamps is also not that elegant and maybe also not faster.
Did you consider it ? Compare performance ?

Sven



Reply | Threaded
Open this post in threaded view
|

Re: [ANN] LRUDictionary

NorbertHartl

Am 11.05.2012 um 16:48 schrieb Sven Van Caekenberghe:

> Hi Norbert,
>
> On 11 May 2012, at 14:51, Norbert Hartl wrote:
>
>> I like to announce a tiny utility I did for my last project. It is only a single class that basically works like LRUCache internally but on the outside it is more like a dictionary. And it has no factory block.
>>
>> If you don't know LRUCache, it's a fixed size dictionary that sorts its elements by usage in a "Least Recently Used" fashion. Meaning the last used element is put in front and the least used at the end. Elements get discarded at the end if space is full.
>>
>> Apart from #at: that is provided by LRUCache , LRUDictionary implements to following methods
>>
>> at:ifAbsent:
>> at:ifAbsentPut:
>> at:ifPresent:
>> at:put:
>> removeAt:
>> removeKey:
>> removeKey:ifAbsent
>>
>> It is available here
>>
>> MCHttpRepository
>> location: 'http://source.selfish.org/mc/misc'
>> user: ''
>> password: ''
>>
>> Blog article is here
>>
>> http://norbert.hartl.name/blog/lrudictionary/
>>
>> hope you like it,
>>
>> Norbert
>
> This code strikes me as less than optimal:
>
> putInFront: anObject fromIndex: aNumber
> values
> replaceFrom: 2
> to: aNumber
> with: (values first: aNumber - 1).
> values at: 1 put: anObject.
> ^ anObject
>
> #first: does a copy no ?
>
> #replaceFrom:to:with:startingAt: can do in place shifting, if you are careful.
> I would also optimize for the case when the object is already in front.

Sven,

to be honest I didn't think about it. The part you are mentioning I took straight from LRUCache without doubting its usefulness. Everything you say makes sense to me. But I need to think first before saying anything useful :)
>
> But even then, all this shifting on each #at: access is a bit costly for a cache, no ?
> The alternative, working with timestamps is also not that elegant and maybe also not faster.
> Did you consider it ? Compare performance ?

Of course the shifting is costly. I use it as a cache for outoging rest calls that does http and deserializes data. From that point of view it's no question. It accelerates immensly and the costs are leveraged easily. The timestamp approach needs to be tested. But I think you are right. It sounds much better to have to scan the array if an old element has to be removed instead of every access.

Norbert