Re: [PHP-DEV] Zend fast cache
At 07:17 PM 11/30/2002 -0500, Sterling Hughes wrote: hrm. :) My only question is really about sequential accesses. for the purpose of example let's pretend its just for zvals... (pool is our pool array of zval structs) ALLOC_ZVAL() - Do we have a zval available? - yes! - return pool[0][0] ALLOC_ZVAL() ... - return pool[0][1] ALLOC_ZVAL() ... - return pool[0][2] FREE_ZVAL() - Clear memory @ pool[0][1] ALLOC_ZVAL() - Do we have a zval available? - return pool[0][3] or do we return pool[0][1] The problem I see with an array approach from an api perspective is simply when a bucket is free'd, in order to have efficient memory usage, we'd need a second level array scan for every ALLOC_ZVAL(). Perhaps a linked list would be a better choice for this, as we can just be smart about bucket access, and eliminate the need for a scan (could be possible I'm missing something?) I think I was misunderstood. Of course I would want a free list. Check out the objects_store code in ZE2. The idea is to have something similar. When we free allocated buckets we add them to a linked list. The linked list is inside the structure itself, i.e., when the bucket isn't used we can use its memory for the pointer to the next element. So allocation just takes the bucket out of the free list. So basically the bucket is a union between sizeof(zval) and sizeof(*) (or sizeof(int)). If it's still not clear I can explain it in a longer letter later on. Ok, i understand - you basically are doing the linked list approach, but using a two-tiered storage paradigm to avoid fragmentation? My only thought now is the dirty specifics: 1) Thread-safety: Will we have to mutex access to this cache? We shouldn't get corruption (I'd assume that on threaded environments we'd use a shared cache) if we have multiple accesses, and if we mutex, we might as well malloc(). 2) Growing buffer sizes. Say we have a _really_ intensive script that does make us grow our zval/object/hashtable cache substantially, however, it is run once every blue moon. Do we after execution is finished than realloc() that huge buffer back down to a normal size? Or perhaps we should just malloc() after a certain size is reached (ok, 16k of prealloc'd stuff, if we don't have a free slot, just do uncached mallocs). -Sterling -- PHP Development Mailing List http://www.php.net/ To unsubscribe, visit: http://www.php.net/unsub.php
Re: [PHP-DEV] Zend fast cache
At 05:27 PM 12/1/2002 -0500, Sterling Hughes wrote: At 07:17 PM 11/30/2002 -0500, Sterling Hughes wrote: hrm. :) My only question is really about sequential accesses. for the purpose of example let's pretend its just for zvals... (pool is our pool array of zval structs) ALLOC_ZVAL() - Do we have a zval available? - yes! - return pool[0][0] ALLOC_ZVAL() ... - return pool[0][1] ALLOC_ZVAL() ... - return pool[0][2] FREE_ZVAL() - Clear memory @ pool[0][1] ALLOC_ZVAL() - Do we have a zval available? - return pool[0][3] or do we return pool[0][1] The problem I see with an array approach from an api perspective is simply when a bucket is free'd, in order to have efficient memory usage, we'd need a second level array scan for every ALLOC_ZVAL(). Perhaps a linked list would be a better choice for this, as we can just be smart about bucket access, and eliminate the need for a scan (could be possible I'm missing something?) I think I was misunderstood. Of course I would want a free list. Check out the objects_store code in ZE2. The idea is to have something similar. When we free allocated buckets we add them to a linked list. The linked list is inside the structure itself, i.e., when the bucket isn't used we can use its memory for the pointer to the next element. So allocation just takes the bucket out of the free list. So basically the bucket is a union between sizeof(zval) and sizeof(*) (or sizeof(int)). If it's still not clear I can explain it in a longer letter later on. Ok, i understand - you basically are doing the linked list approach, but using a two-tiered storage paradigm to avoid fragmentation? My only thought now is the dirty specifics: 1) Thread-safety: Will we have to mutex access to this cache? We shouldn't get corruption (I'd assume that on threaded environments we'd use a shared cache) if we have multiple accesses, and if we mutex, we might as well malloc(). This pool would be per-thread. 2) Growing buffer sizes. Say we have a _really_ intensive script that does make us grow our zval/object/hashtable cache substantially, however, it is run once every blue moon. Do we after execution is finished than realloc() that huge buffer back down to a normal size? Or perhaps we should just malloc() after a certain size is reached (ok, 16k of prealloc'd stuff, if we don't have a free slot, just do uncached mallocs). We'd recreate the cache ever request. It wouldn't cost very much. By the way, I think you did misunderstand me. In my way there wouldn't be a huge buffer. We'd have X buffers. Basically my idea was a two-dimensional array: arr[0] - buffer of size n arr[1] - buffer of size n arr[2] - buffer of size n arr[3] - buffer of size n . And we allocate buffers as needed. Block 1*n+4 would be in arr[1] slot 5 Andi -- PHP Development Mailing List http://www.php.net/ To unsubscribe, visit: http://www.php.net/unsub.php
[PHP-DEV] Zend fast cache
Hey, I was checking the CVS logs, and I read :: revision 1.13 date: 2001/11/26 17:27:59; author: andi; state: Exp; lines: +1 -1 - Turn off fast cache until we make sure it performs well. - The best solution is probably to limit its size. I was just wondering what was wrong, and what it would take to get this thing up and running... Thies and I were looking at a little hack, similiar in nature to this, with preallocating a pool of zval's, and it yielded a 5% performance increase (all hacking credit goes to thies btw :). If we preallocated some basic, often used types, i think we'd get a nice performance increase, perhaps even if we initialized in sapi modes a few structures in MINIT, we could reuse those instead of creating and destroying which is currently quite expensive? -Sterling -- PHP Development Mailing List http://www.php.net/ To unsubscribe, visit: http://www.php.net/unsub.php
Re: [PHP-DEV] Zend fast cache
At 02:59 PM 11/30/2002 -0500, Sterling Hughes wrote: Hey, I was checking the CVS logs, and I read :: revision 1.13 date: 2001/11/26 17:27:59; author: andi; state: Exp; lines: +1 -1 - Turn off fast cache until we make sure it performs well. - The best solution is probably to limit its size. I was just wondering what was wrong, and what it would take to get this thing up and running... Thies and I were looking at a little hack, similiar in nature to this, with preallocating a pool of zval's, and it yielded a 5% performance increase (all hacking credit goes to thies btw :). First of all, let me just say that I wouldn't be too excited about 5% performance difference either way. I already told Thies that from my experience 5% is within the error margin and can change according to compile flags, platform and so on. The reason why the fast cache didn't work well was because it created quite a bit of memory fragmentation which killed MT servers and also made PHP take up too much memory. If we preallocated some basic, often used types, i think we'd get a nice performance increase, perhaps even if we initialized in sapi modes a few structures in MINIT, we could reuse those instead of creating and destroying which is currently quite expensive? That said, I do think that if we can get very fast code to pre-allocate zval's it would be a good idea (hopefully we could get more than 5% increase). I already have an idea for how I would want such an API to look like and I was planning to write it. It would also be useful for Zend objects which are preallocated today but if a realloc() were to be reached it would take quite some time (although one or two realloc()'s wouldn't be terrible). My idea is a two dimensional array. We'd allocate 2^n of memory blocks and assign it to array[0]. Once these are full we'd allocate another 2^n memory blocks and realloc() array to size of 2 and make array[1] point to it. The index to a block would be X and to find the right position it'd be array[X/2^n][X%2^n] of course as the length of each array is a power of two we wouldn't actually need to use division and modulo so it'd be fast. As we don't have templates in C we might be able to put all of this inline in a header file and with macros create such a fast allocating pool for some of the most used types specifically I think it'd be useful for zval's, objects and possible hash tables. I wouldn't overdo the amount of types I'd add to this pool because unless they are allocated and freed extremely often we wouldn't notice a speed difference. But remember what I said about 5% :) Andi -- PHP Development Mailing List http://www.php.net/ To unsubscribe, visit: http://www.php.net/unsub.php
Re: [PHP-DEV] Zend fast cache
At 02:59 PM 11/30/2002 -0500, Sterling Hughes wrote: Hey, I was checking the CVS logs, and I read :: revision 1.13 date: 2001/11/26 17:27:59; author: andi; state: Exp; lines: +1 -1 - Turn off fast cache until we make sure it performs well. - The best solution is probably to limit its size. I was just wondering what was wrong, and what it would take to get this thing up and running... Thies and I were looking at a little hack, similiar in nature to this, with preallocating a pool of zval's, and it yielded a 5% performance increase (all hacking credit goes to thies btw :). First of all, let me just say that I wouldn't be too excited about 5% performance difference either way. I already told Thies that from my experience 5% is within the error margin and can change according to compile flags, platform and so on. perhaps... this was 5% worse case though, comparing to similairly compiled source trees. In some cases it yielded 15-30% percent, but that can be as you say, attributed to flukes. Still, it would follow that having a memory cache would be a good thing, even if it does only show 5% (on a small script btw)... The reason why the fast cache didn't work well was because it created quite a bit of memory fragmentation which killed MT servers and also made PHP take up too much memory. If we preallocated some basic, often used types, i think we'd get a nice performance increase, perhaps even if we initialized in sapi modes a few structures in MINIT, we could reuse those instead of creating and destroying which is currently quite expensive? That said, I do think that if we can get very fast code to pre-allocate zval's it would be a good idea (hopefully we could get more than 5% increase). I already have an idea for how I would want such an API to look like and I was planning to write it. It would also be useful for Zend objects which are preallocated today but if a realloc() were to be reached it would take quite some time (although one or two realloc()'s wouldn't be terrible). no it wouldn't, and you've also gotta look @ this in terms of what would cause a realloc(), for example, say we have a 16 k pool, hardly anything, and yet we'd need to have _a ton_ of concurrently allocated zvals in order to fill that up. Plus, while the realloc would be expensive, it would be better than doing that many mallocs. Anyhow, we pretty much agree, soo :) My idea is a two dimensional array. We'd allocate 2^n of memory blocks and assign it to array[0]. Once these are full we'd allocate another 2^n memory blocks and realloc() array to size of 2 and make array[1] point to it. The index to a block would be X and to find the right position it'd be array[X/2^n][X%2^n] of course as the length of each array is a power of two we wouldn't actually need to use division and modulo so it'd be fast. As we don't have templates in C we might be able to put all of this inline in a header file and with macros create such a fast allocating pool for some of the most used types specifically I think it'd be useful for zval's, objects and possible hash tables. I wouldn't overdo the amount of types I'd add to this pool because unless they are allocated and freed extremely often we wouldn't notice a speed difference. But remember what I said about 5% :) hrm. :) My only question is really about sequential accesses. for the purpose of example let's pretend its just for zvals... (pool is our pool array of zval structs) ALLOC_ZVAL() - Do we have a zval available? - yes! - return pool[0][0] ALLOC_ZVAL() ... - return pool[0][1] ALLOC_ZVAL() ... - return pool[0][2] FREE_ZVAL() - Clear memory @ pool[0][1] ALLOC_ZVAL() - Do we have a zval available? - return pool[0][3] or do we return pool[0][1] The problem I see with an array approach from an api perspective is simply when a bucket is free'd, in order to have efficient memory usage, we'd need a second level array scan for every ALLOC_ZVAL(). Perhaps a linked list would be a better choice for this, as we can just be smart about bucket access, and eliminate the need for a scan (could be possible I'm missing something?) -Sterling -- PHP Development Mailing List http://www.php.net/ To unsubscribe, visit: http://www.php.net/unsub.php
Re: [PHP-DEV] Zend fast cache
How does searching the freelist work in this? How is this faster than say a 3-level page table implementation? That said, I do think that if we can get very fast code to pre-allocate zval's it would be a good idea (hopefully we could get more than 5% increase). I already have an idea for how I would want such an API to look like and I was planning to write it. It would also be useful for Zend objects which are preallocated today but if a realloc() were to be reached it would take quite some time (although one or two realloc()'s wouldn't be terrible). My idea is a two dimensional array. We'd allocate 2^n of memory blocks and assign it to array[0]. Once these are full we'd allocate another 2^n memory blocks and realloc() array to size of 2 and make array[1] point to it. The index to a block would be X and to find the right position it'd be array[X/2^n][X%2^n] of course as the length of each array is a power of two we wouldn't actually need to use division and modulo so it'd be fast. As we don't have templates in C we might be able to put all of this inline in a header file and with macros create such a fast allocating pool for some of the most used types specifically I think it'd be useful for zval's, objects and possible hash tables. I wouldn't overdo the amount of types I'd add to this pool because unless they are allocated and freed extremely often we wouldn't notice a speed difference. But remember what I said about 5% :) Andi -- PHP Development Mailing List http://www.php.net/ To unsubscribe, visit: http://www.php.net/unsub.php -- PHP Development Mailing List http://www.php.net/ To unsubscribe, visit: http://www.php.net/unsub.php
Re: [PHP-DEV] Zend fast cache
On Saturday, November 30, 2002, at 07:17 PM, Sterling Hughes wrote: The problem I see with an array approach from an api perspective is simply when a bucket is free'd, in order to have efficient memory usage, we'd need a second level array scan for every ALLOC_ZVAL(). Perhaps a linked list would be a better choice for this, as we can just be smart about bucket access, and eliminate the need for a scan (could be possible I'm missing something?) I agree, a singly linked list seems like a no-brainer; it's an ideal memory-pool data structure because inserts and deletes occur only at the front of the list (so they're constant-time), the links are free, and the implementation is straightforward. -- PHP Development Mailing List http://www.php.net/ To unsubscribe, visit: http://www.php.net/unsub.php
Re: [PHP-DEV] Zend fast cache
The problem I see with an array approach from an api perspective is simply when a bucket is free'd, in order to have efficient memory usage, we'd need a second level array scan for every ALLOC_ZVAL(). Perhaps a linked list would be a better choice for this, as we can just be smart about bucket access, and eliminate the need for a scan (could be possible I'm missing something?) A number of memory allocators use a multi-tiered page table for this. basically for each object type you have a array of N pointers to level 1 objects and a freelist for them, basically tier one has N elements that each contain a freelist bitmask value and an array of pointers to level 2 objects. Level 2 objects have a freelist of N allocations for the desired object type and pointers to each of them. This may be what Andi was talking about, but it wasn't clear to me from his description. So you get N^3 aloocations you can track, and a freelist search involves looking at 3 bitmasks. Significantly faster than a linked list implementation. By keeping a separate tree for each allocation type (or at least allocation size), you also end up with basically no fragmentation. -Sterling -- PHP Development Mailing List http://www.php.net/ To unsubscribe, visit: http://www.php.net/unsub.php -- PHP Development Mailing List http://www.php.net/ To unsubscribe, visit: http://www.php.net/unsub.php
Re: [PHP-DEV] Zend fast cache
A little off-list discussion has sold me on the linked list implementation. Seems very fast and very simple. George On Saturday, November 30, 2002, at 07:53 PM, Daniel Cowgill wrote: On Saturday, November 30, 2002, at 07:17 PM, Sterling Hughes wrote: The problem I see with an array approach from an api perspective is simply when a bucket is free'd, in order to have efficient memory usage, we'd need a second level array scan for every ALLOC_ZVAL(). Perhaps a linked list would be a better choice for this, as we can just be smart about bucket access, and eliminate the need for a scan (could be possible I'm missing something?) I agree, a singly linked list seems like a no-brainer; it's an ideal memory-pool data structure because inserts and deletes occur only at the front of the list (so they're constant-time), the links are free, and the implementation is straightforward. -- PHP Development Mailing List http://www.php.net/ To unsubscribe, visit: http://www.php.net/unsub.php -- PHP Development Mailing List http://www.php.net/ To unsubscribe, visit: http://www.php.net/unsub.php
Re: [PHP-DEV] Zend fast cache
On Sat, 30 Nov 2002, George Schlossnagle wrote: A little off-list discussion has sold me on the linked list implementation. Seems very fast and very simple. O(1) operations are hard to beat. Note that free lists are not primarily about speed, they are also an extremely helpful tool in the fight against memory fragmentation. That said, IRCG has been using single-linked lists for its free lists (3 or 4 data structures) since its inception. I'm moving IRCG right now to a multi-process model and still need to evaluate whether a central free list (based in shared memory and protected by a semaphore) actually works that well. For example, lock contention issues could affect the performance. Some systems in the kernel world use per-node (=CPU) locks which might prove to be a necessary step for applications as well. - Sascha -- PHP Development Mailing List http://www.php.net/ To unsubscribe, visit: http://www.php.net/unsub.php
Re: [PHP-DEV] Zend fast cache
At 07:17 PM 11/30/2002 -0500, Sterling Hughes wrote: hrm. :) My only question is really about sequential accesses. for the purpose of example let's pretend its just for zvals... (pool is our pool array of zval structs) ALLOC_ZVAL() - Do we have a zval available? - yes! - return pool[0][0] ALLOC_ZVAL() ... - return pool[0][1] ALLOC_ZVAL() ... - return pool[0][2] FREE_ZVAL() - Clear memory @ pool[0][1] ALLOC_ZVAL() - Do we have a zval available? - return pool[0][3] or do we return pool[0][1] The problem I see with an array approach from an api perspective is simply when a bucket is free'd, in order to have efficient memory usage, we'd need a second level array scan for every ALLOC_ZVAL(). Perhaps a linked list would be a better choice for this, as we can just be smart about bucket access, and eliminate the need for a scan (could be possible I'm missing something?) I think I was misunderstood. Of course I would want a free list. Check out the objects_store code in ZE2. The idea is to have something similar. When we free allocated buckets we add them to a linked list. The linked list is inside the structure itself, i.e., when the bucket isn't used we can use its memory for the pointer to the next element. So allocation just takes the bucket out of the free list. So basically the bucket is a union between sizeof(zval) and sizeof(*) (or sizeof(int)). If it's still not clear I can explain it in a longer letter later on. Andi -- PHP Development Mailing List http://www.php.net/ To unsubscribe, visit: http://www.php.net/unsub.php
