You are viewing a plain text version of this content. The canonical link for it is here.
Posted to slide-dev@jakarta.apache.org by Oliver Zeigermann <ol...@gmail.com> on 2004/10/22 20:54:59 UTC
Fwd: [Collections] DFAMap? (LONG)
Folks,
this is my brain storm Friday as it seems ;)
I had a closer look at how invalidation of caches works and thought
that might be pretty slow when there are a lot of entries. Abstracting
from the idea of a hierarchical cache I was posting this to the
commons dev list.
Does not seem anyone could make any sense of it there. Maybe someone here...
Is it just non sense?
Oliver
---------- Forwarded message ----------
From: Oliver Zeigermann <ol...@gmail.com>
Date: Tue, 19 Oct 2004 07:30:44 +0200
Subject: [Collections] DFAMap? (LONG)
To: Jakarta Commons Developers List <co...@jakarta.apache.org>
Folks,
while thinking about cache invalidation strategies in the Slide
project a long abandoned idea come back to my mind: a DFA based map
for String keys only! When I implemented a scetch of this once it
turned out to be slower in all respects than hash maps. These are my
old measurements:
DFA: 100000 puts: 5,7 secs / 100000 gets: 1 sec
HashMap: 100000 puts: 3,2 secs / 100000 gets: .661 sec
Even hand tuned versions could not catch up (no measurements - I guess
I was too frustrated at that time).
Anyway, what I need now is a map *plus* something that returns all
values of the keys that have a certain prefix. E.g. if I have three
entries like
olli -> v1
olli2 -> v2
ollo -> v3
the prefix of "oll" would get me v1,v2,v3; "olli" would get me v1,v2; etc.
Now when the number of entries is small you could just iterate over
the entries and do something like a startsWith and collect the values.
In a scenario with thousands or even millions of entries with frequent
checks this is prohibitive, though.
Coming to the point now, when I organise the look up as a DFA the
search space for prefixed values should be dramatically decreased! The
map DFA would be some sort of tree and classes might look like this.
class DFAState {
Object value;
Edge[] mapping;
}
class Edge {
char label;
DFAState nextState;
}
Every state would have an associated value and a number of outgoing
edges to other states. Upon lookup they can be traversed when the next
character is the labeled one. There can at most be one character per
label, so this is deterministic.
If there is no such label then the look fails. If the whole key has
been matched the look up value is the one associated with the DFA.
Those states are called end states. All other states have no
associated value.
Applied to the example above the DFA might look like this. s{i} are
state names, |s{i}| are end state, - are edges. Above and below the
edges, I have put the labels.
o l l i 2
s1 - s2 - s3 - s4 - |s5| - |s6|
\
o |s7|
(hope this makes sense to anyone)
Now, suppose the prefix is "oll". Traversing the DFA would bring me to
s4. Doing a simple depth first search from there for all reachable end
states (s5,s6,s7) will return me all entries having this prefix, i.e.
v1,v2,v3. "olli" would bring me to s5 and the end states reachable
from there (s5,s6) will bring me the v1,v2.
And there I am...
In case anyone has read this through, does it make sense? Or should I
start taking those pills?
Oliver
---------------------------------------------------------------------
To unsubscribe, e-mail: slide-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: slide-dev-help@jakarta.apache.org
Re: [Collections] DFAMap? (LONG)
Posted by Oliver Zeigermann <ol...@gmail.com>.
Folks,
tests showed that all this is not practical. I had two test cases
running where first I created 100000 key/value pairs with the pattern:
"key-" + i
"value-" + i
stored them and retrieved them. The results look promissing:
HashMap:
put/get: 300 / 190 ms
TableDFAMap:
put/get: 360 / 190 ms
DFAMap:
put/get: 460 / 250 ms
However, this works fine only as all keys have common prefixes keeping
the number of states low. If I, however, revers the pattern like:
i + "-key"
i + "-value"
the HashMap does not seem to be too much affected, but both map
implementations fail with an out of memory error as there are sooo
many expanded states.
Anyway, I took the freedom to add my initial implementation of the DFA
map implementations to the proposals section if anyone is interested.
If there was a sandbox section I would have added it there...
I will remove it ASAP if anyone feels it should not be there.
Oliver
On Mon, 25 Oct 2004 19:16:56 +0200, Unico Hommes <un...@hippo.nl> wrote:
> Oliver Zeigermann wrote:
>
> >This impresses me, as I really have almost the same code for a hand
> >optimized version for speed comparision against HashMap! By the way:
> >HashMap still wins the get/put competition :(
> >
> >
> >
>
> Wow, are these the comparisons you posted earlier? I guess it's the
> overhead created by the larger number of method calls.
>
> >However, this only works when your character set is stricly ASCII,
> >otherwise you would need something like
> >
> >new DFAState[65536];
> >
> >right? If so this is prohibitive, I guess...
> >
> >
> >
>
> Yep, having a 2 byte long array for every state would be rather
> expensive. Perhaps there is way to add ranges of chars as the need
> arises. If a char is added that is out of range a new segment is created
> for it.
>
> >Concerning caching: it might indeed by a better idea to have somehing
> >like groups you can invalidate as a bunch. With our cache a path would
> >make a group, versions of a resource as well.
> >
> >
> >
>
> Hmm yes, the caching use case is a special case that can be treated
> differently from the general scenario. Perhaps the EHCache functionality
> James pointed out is a good starting point.
>
> >Anyway, I will inverst more work into the DFAMap as it at least is fun :)
> >
> >
>
> :-)
>
> --
> Unico
>
> >Oliver
> >
> >On Mon, 25 Oct 2004 15:41:51 +0200, Unico Hommes <un...@hippo.nl> wrote:
> >
> >
> >>Pretty cool stuff Oliver. I've had a few occasions in the past when I
> >>wondered whether something like this existed. I never managed to
> >>translate my requirements into an actual design though.
> >>
> >>If memory is no concern and/or you are willing to accept to work with
> >>only a small subset of chars, what about the following alternative
> >>implementation?
> >>
> >>DFAState {
> >> Object value;
> >> DFAState[] successors = new DFAState[128];
> >> DFAState get(char c) {
> >> successors[(int)c];
> >> }
> >>}
> >>
> >>That should speed things up considerably.
> >>
> >>--
> >>Unico
> >>
> >>
>
> <snip/>
>
> ---------------------------------------------------------------------
>
>
> To unsubscribe, e-mail: slide-dev-unsubscribe@jakarta.apache.org
> For additional commands, e-mail: slide-dev-help@jakarta.apache.org
>
>
---------------------------------------------------------------------
To unsubscribe, e-mail: slide-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: slide-dev-help@jakarta.apache.org
Re: [Collections] DFAMap? (LONG)
Posted by Unico Hommes <un...@hippo.nl>.
Oliver Zeigermann wrote:
>This impresses me, as I really have almost the same code for a hand
>optimized version for speed comparision against HashMap! By the way:
>HashMap still wins the get/put competition :(
>
>
>
Wow, are these the comparisons you posted earlier? I guess it's the
overhead created by the larger number of method calls.
>However, this only works when your character set is stricly ASCII,
>otherwise you would need something like
>
>new DFAState[65536];
>
>right? If so this is prohibitive, I guess...
>
>
>
Yep, having a 2 byte long array for every state would be rather
expensive. Perhaps there is way to add ranges of chars as the need
arises. If a char is added that is out of range a new segment is created
for it.
>Concerning caching: it might indeed by a better idea to have somehing
>like groups you can invalidate as a bunch. With our cache a path would
>make a group, versions of a resource as well.
>
>
>
Hmm yes, the caching use case is a special case that can be treated
differently from the general scenario. Perhaps the EHCache functionality
James pointed out is a good starting point.
>Anyway, I will inverst more work into the DFAMap as it at least is fun :)
>
>
:-)
--
Unico
>Oliver
>
>On Mon, 25 Oct 2004 15:41:51 +0200, Unico Hommes <un...@hippo.nl> wrote:
>
>
>>Pretty cool stuff Oliver. I've had a few occasions in the past when I
>>wondered whether something like this existed. I never managed to
>>translate my requirements into an actual design though.
>>
>>If memory is no concern and/or you are willing to accept to work with
>>only a small subset of chars, what about the following alternative
>>implementation?
>>
>>DFAState {
>> Object value;
>> DFAState[] successors = new DFAState[128];
>> DFAState get(char c) {
>> successors[(int)c];
>> }
>>}
>>
>>That should speed things up considerably.
>>
>>--
>>Unico
>>
>>
<snip/>
---------------------------------------------------------------------
To unsubscribe, e-mail: slide-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: slide-dev-help@jakarta.apache.org
Re: [Collections] DFAMap? (LONG)
Posted by Oliver Zeigermann <ol...@gmail.com>.
This impresses me, as I really have almost the same code for a hand
optimized version for speed comparision against HashMap! By the way:
HashMap still wins the get/put competition :(
However, this only works when your character set is stricly ASCII,
otherwise you would need something like
new DFAState[65536];
right? If so this is prohibitive, I guess...
Concerning caching: it might indeed by a better idea to have somehing
like groups you can invalidate as a bunch. With our cache a path would
make a group, versions of a resource as well.
Anyway, I will inverst more work into the DFAMap as it at least is fun :)
Oliver
On Mon, 25 Oct 2004 15:41:51 +0200, Unico Hommes <un...@hippo.nl> wrote:
>
> Pretty cool stuff Oliver. I've had a few occasions in the past when I
> wondered whether something like this existed. I never managed to
> translate my requirements into an actual design though.
>
> If memory is no concern and/or you are willing to accept to work with
> only a small subset of chars, what about the following alternative
> implementation?
>
> DFAState {
> Object value;
> DFAState[] successors = new DFAState[128];
> DFAState get(char c) {
> successors[(int)c];
> }
> }
>
> That should speed things up considerably.
>
> --
> Unico
>
>
>
> On 22-okt-04, at 20:54, Oliver Zeigermann wrote:
>
> > Folks,
> >
> > this is my brain storm Friday as it seems ;)
> >
> > I had a closer look at how invalidation of caches works and thought
> > that might be pretty slow when there are a lot of entries. Abstracting
> > from the idea of a hierarchical cache I was posting this to the
> > commons dev list.
> >
> > Does not seem anyone could make any sense of it there. Maybe someone
> > here...
> >
> > Is it just non sense?
> >
> > Oliver
> >
> >
> > ---------- Forwarded message ----------
> > From: Oliver Zeigermann <ol...@gmail.com>
> > Date: Tue, 19 Oct 2004 07:30:44 +0200
> > Subject: [Collections] DFAMap? (LONG)
> > To: Jakarta Commons Developers List <co...@jakarta.apache.org>
> >
> >
> > Folks,
> >
> > while thinking about cache invalidation strategies in the Slide
> > project a long abandoned idea come back to my mind: a DFA based map
> > for String keys only! When I implemented a scetch of this once it
> > turned out to be slower in all respects than hash maps. These are my
> > old measurements:
> >
> > DFA: 100000 puts: 5,7 secs / 100000 gets: 1 sec
> > HashMap: 100000 puts: 3,2 secs / 100000 gets: .661 sec
> >
> > Even hand tuned versions could not catch up (no measurements - I guess
> > I was too frustrated at that time).
> >
> > Anyway, what I need now is a map *plus* something that returns all
> > values of the keys that have a certain prefix. E.g. if I have three
> > entries like
> >
> > olli -> v1
> > olli2 -> v2
> > ollo -> v3
> >
> > the prefix of "oll" would get me v1,v2,v3; "olli" would get me v1,v2;
> > etc.
> >
> > Now when the number of entries is small you could just iterate over
> > the entries and do something like a startsWith and collect the values.
> > In a scenario with thousands or even millions of entries with frequent
> > checks this is prohibitive, though.
> >
> > Coming to the point now, when I organise the look up as a DFA the
> > search space for prefixed values should be dramatically decreased! The
> > map DFA would be some sort of tree and classes might look like this.
> >
> > class DFAState {
> > Object value;
> > Edge[] mapping;
> > }
> >
> > class Edge {
> > char label;
> > DFAState nextState;
> > }
> >
> > Every state would have an associated value and a number of outgoing
> > edges to other states. Upon lookup they can be traversed when the next
> > character is the labeled one. There can at most be one character per
> > label, so this is deterministic.
> >
> > If there is no such label then the look fails. If the whole key has
> > been matched the look up value is the one associated with the DFA.
> > Those states are called end states. All other states have no
> > associated value.
> >
> > Applied to the example above the DFA might look like this. s{i} are
> > state names, |s{i}| are end state, - are edges. Above and below the
> > edges, I have put the labels.
> >
> > o l l i 2
> > s1 - s2 - s3 - s4 - |s5| - |s6|
> > \
> > o |s7|
> >
> > (hope this makes sense to anyone)
> >
> > Now, suppose the prefix is "oll". Traversing the DFA would bring me to
> > s4. Doing a simple depth first search from there for all reachable end
> > states (s5,s6,s7) will return me all entries having this prefix, i.e.
> > v1,v2,v3. "olli" would bring me to s5 and the end states reachable
> > from there (s5,s6) will bring me the v1,v2.
> >
> > And there I am...
> >
> > In case anyone has read this through, does it make sense? Or should I
> > start taking those pills?
> >
> > Oliver
> >
> > ---------------------------------------------------------------------
> > To unsubscribe, e-mail: slide-dev-unsubscribe@jakarta.apache.org
> > For additional commands, e-mail: slide-dev-help@jakarta.apache.org
> >
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: slide-dev-unsubscribe@jakarta.apache.org
> For additional commands, e-mail: slide-dev-help@jakarta.apache.org
>
>
---------------------------------------------------------------------
To unsubscribe, e-mail: slide-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: slide-dev-help@jakarta.apache.org
Re: [Collections] DFAMap? (LONG)
Posted by Unico Hommes <un...@hippo.nl>.
Pretty cool stuff Oliver. I've had a few occasions in the past when I
wondered whether something like this existed. I never managed to
translate my requirements into an actual design though.
If memory is no concern and/or you are willing to accept to work with
only a small subset of chars, what about the following alternative
implementation?
DFAState {
Object value;
DFAState[] successors = new DFAState[128];
DFAState get(char c) {
successors[(int)c];
}
}
That should speed things up considerably.
--
Unico
On 22-okt-04, at 20:54, Oliver Zeigermann wrote:
> Folks,
>
> this is my brain storm Friday as it seems ;)
>
> I had a closer look at how invalidation of caches works and thought
> that might be pretty slow when there are a lot of entries. Abstracting
> from the idea of a hierarchical cache I was posting this to the
> commons dev list.
>
> Does not seem anyone could make any sense of it there. Maybe someone
> here...
>
> Is it just non sense?
>
> Oliver
>
>
> ---------- Forwarded message ----------
> From: Oliver Zeigermann <ol...@gmail.com>
> Date: Tue, 19 Oct 2004 07:30:44 +0200
> Subject: [Collections] DFAMap? (LONG)
> To: Jakarta Commons Developers List <co...@jakarta.apache.org>
>
>
> Folks,
>
> while thinking about cache invalidation strategies in the Slide
> project a long abandoned idea come back to my mind: a DFA based map
> for String keys only! When I implemented a scetch of this once it
> turned out to be slower in all respects than hash maps. These are my
> old measurements:
>
> DFA: 100000 puts: 5,7 secs / 100000 gets: 1 sec
> HashMap: 100000 puts: 3,2 secs / 100000 gets: .661 sec
>
> Even hand tuned versions could not catch up (no measurements - I guess
> I was too frustrated at that time).
>
> Anyway, what I need now is a map *plus* something that returns all
> values of the keys that have a certain prefix. E.g. if I have three
> entries like
>
> olli -> v1
> olli2 -> v2
> ollo -> v3
>
> the prefix of "oll" would get me v1,v2,v3; "olli" would get me v1,v2;
> etc.
>
> Now when the number of entries is small you could just iterate over
> the entries and do something like a startsWith and collect the values.
> In a scenario with thousands or even millions of entries with frequent
> checks this is prohibitive, though.
>
> Coming to the point now, when I organise the look up as a DFA the
> search space for prefixed values should be dramatically decreased! The
> map DFA would be some sort of tree and classes might look like this.
>
> class DFAState {
> Object value;
> Edge[] mapping;
> }
>
> class Edge {
> char label;
> DFAState nextState;
> }
>
> Every state would have an associated value and a number of outgoing
> edges to other states. Upon lookup they can be traversed when the next
> character is the labeled one. There can at most be one character per
> label, so this is deterministic.
>
> If there is no such label then the look fails. If the whole key has
> been matched the look up value is the one associated with the DFA.
> Those states are called end states. All other states have no
> associated value.
>
> Applied to the example above the DFA might look like this. s{i} are
> state names, |s{i}| are end state, - are edges. Above and below the
> edges, I have put the labels.
>
> o l l i 2
> s1 - s2 - s3 - s4 - |s5| - |s6|
> \
> o |s7|
>
> (hope this makes sense to anyone)
>
> Now, suppose the prefix is "oll". Traversing the DFA would bring me to
> s4. Doing a simple depth first search from there for all reachable end
> states (s5,s6,s7) will return me all entries having this prefix, i.e.
> v1,v2,v3. "olli" would bring me to s5 and the end states reachable
> from there (s5,s6) will bring me the v1,v2.
>
> And there I am...
>
> In case anyone has read this through, does it make sense? Or should I
> start taking those pills?
>
> Oliver
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: slide-dev-unsubscribe@jakarta.apache.org
> For additional commands, e-mail: slide-dev-help@jakarta.apache.org
>
---------------------------------------------------------------------
To unsubscribe, e-mail: slide-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: slide-dev-help@jakarta.apache.org
Re: Fwd: [Collections] DFAMap? (LONG)
Posted by James Mason <ma...@apache.org>.
On Sat, 2004-10-23 at 00:13, Oliver Zeigermann wrote:
> Ooops, I was thinking of a Deterministic Finite Automaton as a DFA,
> sorry for not making this clear :(
I just mentioned having to look it up so you understand my level of
knowledge in this area :).
>
> Concerning JCS, I thought ehcache was the successor of JCS (or am I
> mixing up things?), so maybe it has all this as well? If so the long
> term plan might be to replace my stupid cache with ehcache so there is
> less to maintain... Do you know if there is any way of having
> transactions in ehcache? Or would be have to build transaction support
> around it?
The documentation for ehcache does mention that it started as a set of
patches for JCS and that JCS doesn't appear to be maintained anymore. I
don't know if it qualifies as the successor or not, though. The only
reason I brought up JCS is that I thought you might be able to look at
the code that implemented the grouping to see how someone else solved
the problem.
As for moving to ehcache, I only see two advantages: 1) wider testing
since other projects use the library, and 2) ehcache supports
persistence to disk for large caches. I don't think ehcache has built-in
support for transactions, but I think it's the recommended cache for
Hibernate (which does support transactions) so it's at least possible.
If you want to move in that direction I think it might be a good idea to
have a pluggable cache interface. It would be cool to be able to use
OSCache since it supports distributed caches (OJB does something like
this).
-James
>
> Oliver
>
> On Fri, 22 Oct 2004 22:32:57 -0700, James Mason <ma...@apache.org> wrote:
> > It sounds reasonable to me, but then I had to look up what DFA stands
> > for :) (http://www.netaxs.com/people/nerp/automata/dfa0.html).
> >
> > This also made me remember something I read:
> > http://jakarta.apache.org/turbine/jcs/JCSandJCACHE.html. JCS supports
> > "group" caching using ":" to separate groups. So "org:apache" could be
> > invalidated by calling remove("org:"). I don't know how it's implemented
> > but there might be useable ideas there for you.
> >
> > -James
> >
> >
> >
> > On Fri, 2004-10-22 at 11:54, Oliver Zeigermann wrote:
> > > Folks,
> > >
> > > this is my brain storm Friday as it seems ;)
> > >
> > > I had a closer look at how invalidation of caches works and thought
> > > that might be pretty slow when there are a lot of entries. Abstracting
> > > from the idea of a hierarchical cache I was posting this to the
> > > commons dev list.
> > >
> > > Does not seem anyone could make any sense of it there. Maybe someone here...
> > >
> > > Is it just non sense?
> > >
> > > Oliver
> > >
> > >
> > > ---------- Forwarded message ----------
> > > From: Oliver Zeigermann <ol...@gmail.com>
> > > Date: Tue, 19 Oct 2004 07:30:44 +0200
> > > Subject: [Collections] DFAMap? (LONG)
> > > To: Jakarta Commons Developers List <co...@jakarta.apache.org>
> > >
> > >
> > > Folks,
> > >
> > > while thinking about cache invalidation strategies in the Slide
> > > project a long abandoned idea come back to my mind: a DFA based map
> > > for String keys only! When I implemented a scetch of this once it
> > > turned out to be slower in all respects than hash maps. These are my
> > > old measurements:
> > >
> > > DFA: 100000 puts: 5,7 secs / 100000 gets: 1 sec
> > > HashMap: 100000 puts: 3,2 secs / 100000 gets: .661 sec
> > >
> > > Even hand tuned versions could not catch up (no measurements - I guess
> > > I was too frustrated at that time).
> > >
> > > Anyway, what I need now is a map *plus* something that returns all
> > > values of the keys that have a certain prefix. E.g. if I have three
> > > entries like
> > >
> > > olli -> v1
> > > olli2 -> v2
> > > ollo -> v3
> > >
> > > the prefix of "oll" would get me v1,v2,v3; "olli" would get me v1,v2; etc.
> > >
> > > Now when the number of entries is small you could just iterate over
> > > the entries and do something like a startsWith and collect the values.
> > > In a scenario with thousands or even millions of entries with frequent
> > > checks this is prohibitive, though.
> > >
> > > Coming to the point now, when I organise the look up as a DFA the
> > > search space for prefixed values should be dramatically decreased! The
> > > map DFA would be some sort of tree and classes might look like this.
> > >
> > > class DFAState {
> > > Object value;
> > > Edge[] mapping;
> > > }
> > >
> > > class Edge {
> > > char label;
> > > DFAState nextState;
> > > }
> > >
> > > Every state would have an associated value and a number of outgoing
> > > edges to other states. Upon lookup they can be traversed when the next
> > > character is the labeled one. There can at most be one character per
> > > label, so this is deterministic.
> > >
> > > If there is no such label then the look fails. If the whole key has
> > > been matched the look up value is the one associated with the DFA.
> > > Those states are called end states. All other states have no
> > > associated value.
> > >
> > > Applied to the example above the DFA might look like this. s{i} are
> > > state names, |s{i}| are end state, - are edges. Above and below the
> > > edges, I have put the labels.
> > >
> > > o l l i 2
> > > s1 - s2 - s3 - s4 - |s5| - |s6|
> > > \
> > > o |s7|
> > >
> > > (hope this makes sense to anyone)
> > >
> > > Now, suppose the prefix is "oll". Traversing the DFA would bring me to
> > > s4. Doing a simple depth first search from there for all reachable end
> > > states (s5,s6,s7) will return me all entries having this prefix, i.e.
> > > v1,v2,v3. "olli" would bring me to s5 and the end states reachable
> > > from there (s5,s6) will bring me the v1,v2.
> > >
> > > And there I am...
> > >
> > > In case anyone has read this through, does it make sense? Or should I
> > > start taking those pills?
> > >
> > > Oliver
> > >
> > > ---------------------------------------------------------------------
> > > To unsubscribe, e-mail: slide-dev-unsubscribe@jakarta.apache.org
> > > For additional commands, e-mail: slide-dev-help@jakarta.apache.org
> > >
> > >
> >
> >
>
---------------------------------------------------------------------
To unsubscribe, e-mail: slide-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: slide-dev-help@jakarta.apache.org