zend_fast_hash

php.internals

Sterling Hughes

23 years ago
Hi, I've implemented a very lightweight, efficient hash table for zend engine 2. This is a table that's appropriate for usage in many of the areas where then Zend hash table implementation is unnecessarily complex (which is pretty much everywhere except for PHP arrays themselves.) I've attached the implementation, and a patch which integrates the new hashtable implementation with Zend, including a "case-study," where I've converted over EG(included_files) to use the new hashtable implementation. Right now the hash table code is very simple, as its just there for initial perusal, it can of course be improved upon. So, when can I integrate it? ;-) -Sterling
-- "A business that makes nothing but money is a poor kind of business." - Henry Ford

Zeev Suraski

23 years ago
Can you explain how it is simpler? :) Writing a lightweight hash has been on our mind for quite some time, but the reason it never happened is that it appears that most of the places that use hashes actually do take advantage of the non-bare-bones features. The biggest difference I can spot is that there's no linked list that links all of the elements. But if we end up adding apply, and clean (which are actually used a lot outside the scope of symbol tables), and soon enough we'd also need merge, copy and unnamed elements - I'm not sure it's worth the trouble of having two different APIs. Feel free to convince us :) Zeev At 16:33 21.05.2003, Sterling Hughes wrote:

Sterling Hughes

23 years ago
On Wed, 2003-05-21 at 11:49, Zeev Suraski wrote:
> Can you explain how it is simpler? :) Writing a lightweight hash has been > on our mind for quite some time, but the reason it never happened is that > it appears that most of the places that use hashes actually do take > advantage of the non-bare-bones features. The biggest difference I can > spot is that there's no linked list that links all of the elements. But if > we end up adding apply, and clean (which are actually used a lot outside > the scope of symbol tables), and soon enough we'd also need merge, copy and > unnamed elements - I'm not sure it's worth the trouble of having two
Except for unnamed elements, those are all trivial to implement with the code I've attached. In fact, apply, copy and clean are in there, merge could be done when I figure out the semantics. :) Unnamed elements are impossible, but they should be. If you need unnamed elements, either the code is taking advantage of a feature that shouldn't be there, or one should just use the old hashtable implementation, which will still be available. I dare say that in most cases, using unnamed elements is not necessary. The major API hurdle here is reliance on insertion order, which is used once or twice in the code (not that often, afaik), but I believe that can be changed, and made to work with the new API. I believe I can change over all the symbol tables (EG(function_table), etc.) to use my new hash implementation, and it will be signifigantly faster. I'm holding off on that for now, cause I don't want to muddy the commit/patch. This hashtable implementation requires signifigantly less memory, and has a lower overhead then the standard HashTable. Considering how often hash functions are used in Zend, I think it going to be a big win. -Sterling
-- "First they ignore you, then they laugh at you, then they fight you, then you win." - Gandhi

Andi Gutmans

23 years ago
At 10:37 AM 5/21/2003 -0400, Sterling Hughes wrote:
>On Wed, 2003-05-21 at 11:49, Zeev Suraski wrote: > > Can you explain how it is simpler? :) Writing a lightweight hash has been > > on our mind for quite some time, but the reason it never happened is that > > it appears that most of the places that use hashes actually do take > > advantage of the non-bare-bones features. The biggest difference I can > > spot is that there's no linked list that links all of the > elements. But if > > we end up adding apply, and clean (which are actually used a lot outside > > the scope of symbol tables), and soon enough we'd also need merge, copy > and > > unnamed elements - I'm not sure it's worth the trouble of having two > >Except for unnamed elements, those are all trivial to implement with the >code I've attached. In fact, apply, copy and clean are in there, merge >could be done when I figure out the semantics. :) Unnamed elements are >impossible, but they should be. If you need unnamed elements, either >the code is taking advantage of a feature that shouldn't be there, or >one should just use the old hashtable implementation, which will still >be available. I dare say that in most cases, using unnamed elements is >not necessary.
Let's keep it as simple as possible because if we start adding features it will be zend_hash.*. Only places which need a simple hash should use it and places which need something more powerful should continue to use zend_hash.*
>The major API hurdle here is reliance on insertion order, which is used >once or twice in the code (not that often, afaik), but I believe that >can be changed, and made to work with the new API. I believe I can >change over all the symbol tables (EG(function_table), etc.) to use my >new hash implementation, and it will be signifigantly faster. I'm >holding off on that for now, cause I don't want to muddy the >commit/patch.
I don't think EG(function_table) can use it because I think it uses a reverse_apply().
>This hashtable implementation requires signifigantly less memory, and >has a lower overhead then the standard HashTable. Considering how often >hash functions are used in Zend, I think it going to be a big win.
Yep, it has been on my mind for a while but we need to make sure we do it right. Andi

Sterling Hughes

23 years ago
> >Except for unnamed elements, those are all trivial to implement with the > >code I've attached. In fact, apply, copy and clean are in there, merge > >could be done when I figure out the semantics. :) Unnamed elements are > >impossible, but they should be. If you need unnamed elements, either > >the code is taking advantage of a feature that shouldn't be there, or > >one should just use the old hashtable implementation, which will still > >be available. I dare say that in most cases, using unnamed elements is > >not necessary. > > Let's keep it as simple as possible because if we start adding features it > will be zend_hash.*. Only places which need a simple hash should use it and > places which need something more powerful should continue to use zend_hash.* >
That's my idea at least. Start simple, improve or add features as deemed necessary.
> >The major API hurdle here is reliance on insertion order, which is used > >once or twice in the code (not that often, afaik), but I believe that > >can be changed, and made to work with the new API. I believe I can > >change over all the symbol tables (EG(function_table), etc.) to use my > >new hash implementation, and it will be signifigantly faster. I'm > >holding off on that for now, cause I don't want to muddy the > >commit/patch. > > I don't think EG(function_table) can use it because I think it uses a > reverse_apply(). >
Right. That's a terrible usage for it though (not saying I have a better idea :) It could still be done somewhat efficiently (i prepend elements onto the chains, so you could read each bucket until an internal function is reached.) I don't know though, that would need some benchmarking, I'm not sure which would be more efficient. Still, we can cross that bridge when it comes. -Sterling
-- "A business that makes nothing but money is a poor kind of business." - Henry Ford

Zeev Suraski

23 years ago
At 17:37 21/05/2003, Sterling Hughes wrote:
>Except for unnamed elements, those are all trivial to implement with the >code I've attached. In fact, apply, copy and clean are in there, merge >could be done when I figure out the semantics. :)
I know, and I knew that already :) That's kinda what I fear.
> Unnamed elements are >impossible, but they should be. If you need unnamed elements, either >the code is taking advantage of a feature that shouldn't be there, or >one should just use the old hashtable implementation, which will still >be available. I dare say that in most cases, using unnamed elements is >not necessary. > >The major API hurdle here is reliance on insertion order, which is used >once or twice in the code (not that often, afaik), but I believe that >can be changed, and made to work with the new API. I believe I can >change over all the symbol tables (EG(function_table), etc.) to use my >new hash implementation, and it will be signifigantly faster. I'm >holding off on that for now, cause I don't want to muddy the >commit/patch.
Again, the problem in my opinion is that you will soon find out that without adding all the bells and whistles of the Zend hash table, you won't be able to use it for almost anything. And once you add all the bells and whistles of the Zend hash table, it won't be significantly more light-weight, and won't justify the duplicated code. The 'start simple and add stuff as necessary' held true for the Zend hash too. It started in 1997 as a very simple thing, and what you see now is what we needed to add ever since :)
>This hashtable implementation requires signifigantly less memory, and >has a lower overhead then the standard HashTable. Considering how often >hash functions are used in Zend, I think it going to be a big win.
Looking at it, it appears the the major difference is the removal of the global linked list. I don't think there's going to be a substantial gain in performance, there will be some gain in memory, but if we only use it for 'singular' hashes like function_table, that's going to have negligible effect. One advantage we have today (vs. 1997) is that we know fairly well what we need. I think that before we introduce a second hash to the engine, we should have a pretty good idea about where it could be used, and what kind of effect (gain) it's going to have. If you could come up with a list of places where this hash can be used, plus some numbers as to what kind of gains (in terms of memory and performance) we can expect, I think we'd be in a better position to decide whether this should go in or not. Zeev P.S.: As might be evident from Andi's response, we've actually been discussing this issue for several years now. My position was that we'd find very little usage for this hash, because we've grown to rely on many of the extra features of the Zend hash just about everywhere. Andi's position was, more or less, "there must be something we can do" :) I guess it's showdown time.

Sterling Hughes

23 years ago
> > Unnamed elements are > >impossible, but they should be. If you need unnamed elements, either > >the code is taking advantage of a feature that shouldn't be there, or > >one should just use the old hashtable implementation, which will still > >be available. I dare say that in most cases, using unnamed elements is > >not necessary. > > > >The major API hurdle here is reliance on insertion order, which is used > >once or twice in the code (not that often, afaik), but I believe that > >can be changed, and made to work with the new API. I believe I can > >change over all the symbol tables (EG(function_table), etc.) to use my > >new hash implementation, and it will be signifigantly faster. I'm > >holding off on that for now, cause I don't want to muddy the > >commit/patch. > > Again, the problem in my opinion is that you will soon find out that > without adding all the bells and whistles of the Zend hash table, you won't > be able to use it for almost anything. And once you add all the bells and > whistles of the Zend hash table, it won't be significantly more > light-weight, and won't justify the duplicated code. > The 'start simple and add stuff as necessary' held true for the Zend hash > too. It started in 1997 as a very simple thing, and what you see now is > what we needed to add ever since :) >
I think you misunderestimate HANDLE_NUMERIC(), and some of the other little overheads introduced. I think the major different between the current hashtable implementation and the new one, is that the new one has no intention of being used to facilitate PHP arrays.
> >This hashtable implementation requires signifigantly less memory, and > >has a lower overhead then the standard HashTable. Considering how often > >hash functions are used in Zend, I think it going to be a big win. > > Looking at it, it appears the the major difference is the removal of the > global linked list. I don't think there's going to be a substantial gain > in performance, there will be some gain in memory, but if we only use it > for 'singular' hashes like function_table, that's going to have negligible > effect. >
Singular hashes? There will be a nice gain in memory, and again, I think there will also be a CPU gain, not really signifigant mind you, but zend_hash's are used so often, that I think you'll be surprised at the outcome.
> One advantage we have today (vs. 1997) is that we know fairly well what we > need. I think that before we introduce a second hash to the engine, we > should have a pretty good idea about where it could be used, and what kind > of effect (gain) it's going to have. If you could come up with a list of > places where this hash can be used, plus some numbers as to what kind of > gains (in terms of memory and performance) we can expect, I think we'd be > in a better position to decide whether this should go in or not. >
Ok. I'll take a look at converting some places over.
> Zeev > > P.S.: As might be evident from Andi's response, we've actually been > discussing this issue for several years now. My position was that we'd > find very little usage for this hash, because we've grown to rely on many > of the extra features of the Zend hash just about everywhere. Andi's > position was, more or less, "there must be something we can do" :) I guess > it's showdown time.
I'll save you the suspense. Andi is right ;-) -Sterling
-- "That stuff's easy compared to installing Horde" - Alan Knowles, In response to my applause for creating a LALR parser for PHP.

Andrei Zmievski

23 years ago
On Thu, 22 May 2003, Sterling Hughes wrote:
> I think you misunderestimate HANDLE_NUMERIC(), and some of the other
Misunderestimate? Is that like "overestimate"? -Andrei * Proximity bug: when the program crashes in front of important visitors. *

Sascha Schumann

23 years ago
On Thu, 22 May 2003, Andrei Zmievski wrote:
> On Thu, 22 May 2003, Sterling Hughes wrote: > > I think you misunderestimate HANDLE_NUMERIC(), and some of the other > > Misunderestimate? Is that like "overestimate"?
That is a Bushim, as far as I recall. - Sascha

Sascha Schumann

23 years ago
On Thu, 22 May 2003, Sascha Schumann wrote:
> On Thu, 22 May 2003, Andrei Zmievski wrote: > > > On Thu, 22 May 2003, Sterling Hughes wrote: > > > I think you misunderestimate HANDLE_NUMERIC(), and some of the other > > > > Misunderestimate? Is that like "overestimate"? > > That is a Bushim, as far as I recall.
Bushism even: http://abcnews.go.com/sections/us/WolfFiles/wolffiles249.html - Sascha

Sterling Hughes

23 years ago
On Thu, 2003-05-22 at 09:36, Andrei Zmievski wrote:
> On Thu, 22 May 2003, Sterling Hughes wrote: > > I think you misunderestimate HANDLE_NUMERIC(), and some of the other > > Misunderestimate? Is that like "overestimate"? >
No. That's my favorite George W. Bush quote. [1] When he was elected he said 'They misunderestimated me.' ;-) -Sterling [1] Just letting my inner patriotism shine through! :)
> -Andrei > * Proximity bug: when the program crashes in front of important visitors. *
-- Good judgement comes from experience, and experience comes from bad judgement. - Fred Brooks

Zeev Suraski

23 years ago
At 15:03 22.05.2003, Sterling Hughes wrote:
>I think you misunderestimate HANDLE_NUMERIC(), and some of the other >little overheads introduced. I think the major different between the >current hashtable implementation and the new one, is that the new one >has no intention of being used to facilitate PHP arrays.
I know the reasons for adding it quite well - I'm just less confident that they'll end up bringing substantial gains. Have you benchmarked the two beasts against each other? Do you have some figures as to difference in memory requirements? My point is that while it feels bad to use such a feature-bloated hash for all the stuff that we use it for, I think the gain from switching to something different will be negligible, and won't justify duplicating the code. I could be wrong, it's my educated guess, and others' educated guesses are different. We simply need to check.
> > >This hashtable implementation requires signifigantly less memory, and > > >has a lower overhead then the standard HashTable. Considering how often > > >hash functions are used in Zend, I think it going to be a big win. > > > > Looking at it, it appears the the major difference is the removal of the > > global linked list. I don't think there's going to be a substantial gain > > in performance, there will be some gain in memory, but if we only use it > > for 'singular' hashes like function_table, that's going to have negligible > > effect. > > > >Singular hashes?
Like function_table - you only have a single instance per request, or if you use OO, another one per class (still a relative small number of instances, vs. objects/arrays).
>There will be a nice gain in memory, and again, I think there will also >be a CPU gain, not really signifigant mind you, but zend_hash's are used >so often, that I think you'll be surprised at the outcome.
Maybe. I don't mind if you commit and try to move stuff over, as long as if it ends up not bringing a substantial gain (i.e., less than 5% or so) we (read: you :) would roll back. There's an inherent drawback in duplicating code from a maintenance point of view, so we have to justify that price... Zeev

Sterling Hughes

23 years ago
> >so often, that I think you'll be surprised at the outcome. > > Maybe. I don't mind if you commit and try to move stuff over, as long as > if it ends up not bringing a substantial gain (i.e., less than 5% or so) we > (read: you :) would roll back. There's an inherent drawback in > duplicating code from a maintenance point of view, so we have to justify > that price... >
No problem. I'm going to play with it a bit more locally, but I'll have no problem reverting it, if after playing with the implementation, it turns out we lose speed. -Sterling
-- "The three most dangerous things in the world are a programmer with a soldering iron, a hardware type with a program patch and a user with an idea." - Unknown

Andi Gutmans

23 years ago
I'll try and take a look at it more closely in the next couple of days. I've been wanting to make a fast hash for a while for the parts of PHP which don't need the goodies in the existing one. A few things which I saw right away: a) You can allocate the key as part of the hash element. This will save you an emalloc() per insertion and an efree() per deletion (we do this in zend_hash.*). b) Instead of using modulo (%) you can use bit arithmetic like in zend_hash.*. The hash function is supposed to be good enough. Wanna write up a new patch? Thans, Andi At 09:33 AM 5/21/2003 -0400, Sterling Hughes wrote: