Everything
php
Learn Community Releases The PHP Project
Home » Project » Newsgroups » php.internals » Tree sort in C »

Tree sort in C

php.internals

Brian Moon

19 years ago
A common issue in lots of applications is tree sorting with unlimited depth. Phorum has used a recursive function since 1999 to solve this problem. However, at MySQL Conference this year, we finally wrote a non recursive function for it and acheived both memory and time savings on very large data sets. I always knew it could be done, I had just never stopped and worked it out. Most examples I found involved a left/right model that our data does not use. The left/right model involves altering rows when new rows are inserted into the tree. That is not attractive. Phorum uses just a parent_id field to track child members. We would like to take this to another level and make a PHP internal funciton to do the work. In fact, since MySQL Conference, one of team members has written the function as a PHP extension. My questions is, if we made a generic tree sorting function, could this be a function that we could get considered for addition to the other array sorting functions. I have probably ported the Phorum PHP based for tree sorting over to 100 different other applications for sorting trees in PHP. It would be very nice to finally have an internal function for it. Speed is not our main benefit, although there is a noticable speed boost. In addition to sorting the function, each node would be assigned a depth value (optionally named by a function parameter if needed). This is where the biggest memory savings have been found for us. On large data sets (2000 members) in PHP, we have found that altering the input array would cause copy of the whole array, blowing up the memory usage of the script to as much as 10x. Doing this in C helps to remove that problem. Basically, an array would look like: $array = array( 1 => array( "id" => 1, "parent" => 0, "name" => "item 1" ), 2 => array( "id" => 2, "parent" => 0, "name" => "item 2" ), 3 =>array( "id" => 3, "parent" => 1, "name" => "item 1" ), ); The function call would look like: array_treesort($array, "id", "parent"); The returned array would look like: $array = array( 1 => array( "id" => 1, "parent" => 0, "name" => "item 1", "depth" => 0 ), 3 =>array( "id" => 3, "parent" => 1, "name" => "item 1", "depth" => 1 ), 2 => array( "id" => 2, "parent" => 0, "name" => "item 2", "depth" => 0 ), ); Its a little funky to have a function take names of fields like this, but this is the only way we could think of to make this work for people without them having to change their data structure. You can see our current work at http://www.phorum.org/tracfcgi/browser/phorum5/trunk/extension_src That code has been written specifically for Phorum to replace our existing PHP function. It does more than the PHP internal function would do. But, the extra parts are not the things that we were trying to overcome. They are just gravy.
-- Brian Moon Senior Developer ------------------------------ http://dealnews.com/ It's good to be cheap =)

Richard Quadling

19 years ago
On 09/05/07, Brian Moon <brianm@dealnews.com> wrote:
> A common issue in lots of applications is tree sorting with unlimited > depth. Phorum has used a recursive function since 1999 to solve this > problem. However, at MySQL Conference this year, we finally wrote a non > recursive function for it and acheived both memory and time savings on > very large data sets. I always knew it could be done, I had just never > stopped and worked it out. Most examples I found involved a left/right > model that our data does not use. The left/right model involves > altering rows when new rows are inserted into the tree. That is not > attractive. Phorum uses just a parent_id field to track child members. > > We would like to take this to another level and make a PHP internal > funciton to do the work. In fact, since MySQL Conference, one of team > members has written the function as a PHP extension. My questions is, > if we made a generic tree sorting function, could this be a function > that we could get considered for addition to the other array sorting > functions. I have probably ported the Phorum PHP based for tree sorting > over to 100 different other applications for sorting trees in PHP. It > would be very nice to finally have an internal function for it. > > Speed is not our main benefit, although there is a noticable speed > boost. In addition to sorting the function, each node would be assigned > a depth value (optionally named by a function parameter if needed). > This is where the biggest memory savings have been found for us. On > large data sets (2000 members) in PHP, we have found that altering the > input array would cause copy of the whole array, blowing up the memory > usage of the script to as much as 10x. Doing this in C helps to remove > that problem. > > > Basically, an array would look like: > > $array = array( > 1 => array( > "id" => 1, > "parent" => 0, > "name" => "item 1" > ), > 2 => array( > "id" => 2, > "parent" => 0, > "name" => "item 2" > ), > 3 =>array( > "id" => 3, > "parent" => 1, > "name" => "item 1" > ), > ); > > The function call would look like: > > array_treesort($array, "id", "parent"); > > The returned array would look like: > > $array = array( > 1 => array( > "id" => 1, > "parent" => 0, > "name" => "item 1", > "depth" => 0 > ), > 3 =>array( > "id" => 3, > "parent" => 1, > "name" => "item 1", > "depth" => 1 > ), > 2 => array( > "id" => 2, > "parent" => 0, > "name" => "item 2", > "depth" => 0 > ), > ); > > > Its a little funky to have a function take names of fields like this, > but this is the only way we could think of to make this work for people > without them having to change their data structure. > > You can see our current work at > http://www.phorum.org/tracfcgi/browser/phorum5/trunk/extension_src That > code has been written specifically for Phorum to replace our existing > PHP function. It does more than the PHP internal function would do. > But, the extra parts are not the things that we were trying to overcome. > They are just gravy. > > -- > > Brian Moon > Senior Developer > ------------------------------ > http://dealnews.com/ > It's good to be cheap =) > > -- > PHP Internals - PHP Runtime Development Mailing List > To unsubscribe, visit: http://www.php.net/unsub.php > >
Take a look at http://www.php.net/manual/en/function.array-multisort.php#68689 / http://rquadling.php1h.com/array_multisort_column.php Richard.
-- ----- Richard Quadling Zend Certified Engineer : http://zend.com/zce.php?c=ZEND002498&r=213474731 "Standing on the shoulders of some very clever giants!"

Maurice Makaay

19 years ago
Hello,
> Take a look at > http://www.php.net/manual/en/function.array-multisort.php#68689 > / http://rquadling.php1h.com/array_multisort_column.php
Could you please explain how you think that multisort array would help in doing a tree sort? AFAIK, tree sorting is not a simple sort algorithm where you can tell which node comes before the other based on an $a vs. $b comparison. After playing with it for quite a bit of time, I'm quite convinced that you actually have to walk the tree to find indention levels and node positions. Imagine a tree like this: node id parent id 1 0 (root node) 2 1 3 1 4 2 The tree sort with indention would look like this: 1 2 4 3 This is about as simple as it can get. So the ordered tree nodes for this example would be array(1,2,4,3). Now try to find an array sorting algorithm to get to this result. You'll find that node 4 is quite a nasty one to get your head around. Maybe we missed something obvious here, but there's most probably a reason why a lot of applications implement tree sorting as a recursive function call and not as an array sort of some kind. From your followup post:
> That doesn't look right. Surely ID is already sorted so the array
won't change?
> And sorting by "parent" and then "id" would make no difference either.
I see you already found out the big issue with tree sorting ;-) You cannot apply simple linear sorting to find out in what order the nodes in a tree appear. I hope my example cleared up some of the confusion. With kind regards, Maurice Makaay Phorum.org

Michael Walter

19 years ago
Hi, A quick sketch of an idea that should work: <?php // test data $nodes=array( array('id'=>1, 'parent_id'=>0), array('id'=>2, 'parent_id'=>1), array('id'=>3, 'parent_id'=>1), array('id'=>4, 'parent_id'=>2) ); // create column data $keys=$indents=$index=array(); $i=0; foreach($nodes as $node) { $id=$node['id']; $pid=$node['parent_id']; $index[$id]=$i; $keys[]=$pid ? $keys[$index[$pid]].'_'.$id : $id; $indents[]=$pid ? $indents[$index[$pid]]+1 : 0; ++$i; } // sort array_multisort($keys, $indents, $nodes); // display $i=0; foreach($nodes as $node) echo str_repeat(' ', $indents[$i++]), $node['id'], "\n"; ?> Regards, Michael On 5/9/07, Maurice Makaay <maurice@phorum.org> wrote:

Maurice Makaay

19 years ago
Hi,
> A quick sketch of an idea that should work:
Yes, that would work. The problem though, is that there's still accumulation of data going on, before the actual sorting can take place. Remember that the main reason for writing the C-extension was to get the memory usage down. Here's some benchmarks that I just did between the multisort solution and the extension (time / memory). I commented out the efree() calls in the extension so see the actual memory usage in these benchmarks: 10 nodes extension 4.19616699219E-05 / 756 multisort 0.000128984451294 / 3916 100 nodes extension 0.000138998031616 / 5444 multisort 0.000992059707642 / 32536 1000 nodes extension 0.00320601463318 / 52276 multisort 0.0115978717804 / 320988 5000 nodes extension 0.127704143524 / 260356 multisort 0.0901730060577 / 1594448 10000 nodes extension 0.438856840134 / 520308 multisort 0.172026872635 / 3196832 As you can see, the extension is faster and lighter on memory. At a really large number of nodes, the extension becomes slower, but the memory stays low. It's the memory that bothers my servers the most, not the execution time. With kind regards, Maurice Makaay Phorum.org

Derick Rethans

19 years ago
On Wed, 9 May 2007, Maurice Makaay wrote:
> At a really > large number of nodes, the extension becomes slower, but the memory stays low.
That is very peculiar... it should never be slower than an implementation in PHP - unless your algorithm isn't optimal. regards, Derick

Brian Moon

19 years ago
Derick Rethans wrote:
> On Wed, 9 May 2007, Maurice Makaay wrote: > >> At a really >> large number of nodes, the extension becomes slower, but the memory stays low. > > That is very peculiar... it should never be slower than an > implementation in PHP - unless your algorithm isn't optimal.
Me too. But, fwiw, the multisort method does not do the same thing. So, its apples to oranges. See my other email. In the apples to apples comparisons with use the same algorithm in PHP and in C, the C version is always faster.
-- Brian Moon Senior Developer ------------------------------ http://dealnews.com/ It's good to be cheap =)

Richard Quadling

19 years ago
On 09/05/07, Brian Moon <brianm@dealnews.com> wrote:
> Derick Rethans wrote: > > On Wed, 9 May 2007, Maurice Makaay wrote: > > > >> At a really > >> large number of nodes, the extension becomes slower, but the memory stays low. > > > > That is very peculiar... it should never be slower than an > > implementation in PHP - unless your algorithm isn't optimal. > > Me too. But, fwiw, the multisort method does not do the same thing. > So, its apples to oranges. See my other email. In the apples to apples > comparisons with use the same algorithm in PHP and in C, the C version > is always faster. >
I agree with Brian here, the code I referenced was an array multisort by column which I created based upon user notes on the array_multisort function. You do not require a trawl through to get the list of "keys" like is done here. So, $sorted = array_multisort_column($nodes, 'parent_id', 'id'); It is a single pass mechanism. It uses the indexes supplied to compare them in sequence. A simple bubble sort. BUT this is not a tree sort as this is something quite different. The array_multisort() nor my array_multisort_column() functions will not work for more than 1 level of parent/child relationships. Richard
> -- > > Brian Moon > Senior Developer > ------------------------------ > http://dealnews.com/ > It's good to be cheap =) >
-- ----- Richard Quadling Zend Certified Engineer : http://zend.com/zce.php?c=ZEND002498&r=213474731 "Standing on the shoulders of some very clever giants!"

Maurice Makaay

19 years ago
Hi,
> That is very peculiar... it should never be slower than an > implementation in PHP - unless your algorithm isn't optimal. >
Depends on your definition of "optimal". In setting up the structures, I have a linear search going to find the node for a parent. That's why it gets slower for (very) large quantities of nodes. It would be easy enough to introduce a hashing table there for quick lookups, but of course at the cost of extra memory. I have looked at my forums (since like Brian wrote: the code that we have is targeted at Phorum's message trees) and there I need sorting for up to a several thousand nodes at most. The large majority of the sorts are several hundreds at most. So this code needs no further optimization there. If this would go in the PHP internals, then I asume the function code would probably be balancing between fast processing and little memory use. Regards, Maurice Makaay Phorum.org

Maurice Makaay

19 years ago
Hi,
> That is very peculiar... it should never be slower than an > implementation in PHP - unless your algorithm isn't optimal. >
The timing for large numbers of nodes got slower due to a linear lookup (as explained in a previous message too). I implemented a hash table lookup as a replacement. This still does not use a lot of memory and the speed does no longer decrease at large quantities of nodes. FYI, here are some benchmarks against the multisort routine: 10 nodes extension 8.39233398438E-05 / 1316 multisort 0.0001380443573 / 3808 100 nodes extension 0.00014591217041 / 10416 multisort 0.000678062438965 / 32160 1000 nodes extension 0.000765800476074 / 79868 multisort 0.00885391235352 / 298844 5000 nodes extension 0.00524711608887 / 284572 multisort 0.110008001328 / 1596844 10000 nodes extension 0.0113878250122 / 537368 multisort 0.136567831039 / 3252232 20000 nodes extension 0.0704438686371 / 1042796 multisort 0.370564937592 / 6567656 With kind regards, Maurice Makaay Phorum.org

Pierre Joye

19 years ago
HI Maurice, On 5/10/07, Maurice Makaay <maurice@phorum.org> wrote:
> > That is very peculiar... it should never be slower than an > > implementation in PHP - unless your algorithm isn't optimal. > > > The timing for large numbers of nodes got slower due to a linear lookup > (as explained in a previous message too). I implemented a hash table > lookup as a replacement. This still does not use a lot of memory and the > speed does no longer decrease at large quantities of nodes.
Only for the record, You may have missed it, there was some work done in this area by Sterling a couple of years ago (well, too many ;). He thought there was a need for such functions. He began to work on an extension called advanced data types (adt) in pecl . It may be something you can consider and bring it back to life :) ? Or at least it could be a good idea to continue your work in PECL, in a single tree extension. At some point point, the new functions/classes may be in php or maybe not. But you will at least have a place to stabilize/improve, publish or maintain. Please note that these are only suggestions, I would like to have advance data types like tree (or derived) n php but for what I see, we are not ready yet to understand their importance :) --Pierre

Brian Moon

19 years ago
Maurice Makaay wrote:
> Hi, >> A quick sketch of an idea that should work: > Yes, that would work. The problem though, is that there's still > accumulation of data going on, before the actual sorting can take place. > Remember that the main reason for writing the C-extension was to get the > memory usage down.
Actually, this does not work. It uses string sorting to sort the nodes in the $keys array. This means the nodes at a given level are now out of order compared to the original order of the input array Try this for making a node list: for($x=1;$x<=40;$x++){ $parent = rand(0,$x-1); $nodes[$x] = array( "id" => $x, "parent_id" => $parent, "title" => "item $x" ); } You will see that the order of the nodes within a level is string sorted. That is not desired. The order of the children should not change from the order they appeared in the input array. In this case, numeric, but with our function, the order is preserved. So, you could sort the array by ANY thing you wanted before calling the tree sort function and the nodes at any given level will be in that order. And as Maurice said, the memory overhead is still there.
-- Brian Moon Senior Developer ------------------------------ http://dealnews.com/ It's good to be cheap =)

Richard Lynch

19 years ago
On Wed, May 9, 2007 9:22 am, Brian Moon wrote:
> A common issue in lots of applications is tree sorting with unlimited > depth. Phorum has used a recursive function since 1999 to solve this > problem. However, at MySQL Conference this year, we finally wrote a > non
Seems like you could just make it a custom extension and see if people use it a lot... Even if you just had every phorum user asking for it, that would drive a lot of interest, no?
-- Some people have a "gift" link here. Know what I want? I want you to buy a CD from some indie artist. http://cdbaby.com/browse/from/lynch Yeah, I get a buck. So?

Brian Moon

19 years ago
Richard Lynch wrote:
> Seems like you could just make it a custom extension and see if people > use it a lot... > > Even if you just had every phorum user asking for it, that would drive > a lot of interest, no?
Well, making a custom Phorum extension is a whole other discussion for our team to have. If we went down that road, we would do more than just this function. And with this function in the core or not, we may still do that at some point. My point for wanting it in PHP is that I have used a tree sorting algorithm OUTSIDE of Phorum a lot in my 10 years of PHP coding. There are many many uses outside of Phorum for such a function IMO.
-- Brian Moon Senior Developer ------------------------------ http://dealnews.com/ It's good to be cheap =)

Sebastian Bergmann

19 years ago
Brian Moon schrieb:
> Well, making a custom Phorum extension is a whole other discussion for > our team to have. If we went down that road, we would do more than just > this function.
An extension that provides efficient graph / tree algorithms (the latter are just a special case of the former) would be usefull, IMHO.
-- Sebastian Bergmann http://sebastian-bergmann.de/ GnuPG Key: 0xB85B5D69 / 27A7 2B14 09E4 98CD 6277 0E5B 6867 C514 B85B 5D69

Richard Lynch

19 years ago
On Wed, May 9, 2007 1:00 pm, Brian Moon wrote:
> Richard Lynch wrote: >> Seems like you could just make it a custom extension and see if >> people >> use it a lot... >> >> Even if you just had every phorum user asking for it, that would >> drive >> a lot of interest, no? > > Well, making a custom Phorum extension is a whole other discussion for > our team to have. If we went down that road, we would do more than > just > this function. And with this function in the core or not, we may > still > do that at some point. > > My point for wanting it in PHP is that I have used a tree sorting > algorithm OUTSIDE of Phorum a lot in my 10 years of PHP coding. There > are many many uses outside of Phorum for such a function IMO.
My point is that the path to getting anything into core might be to release a generalized extension that, for your purposes, would be almost as good as having it in core in the short term. Long-term, one of these happens: The extension either "grows" into a full-blow extension with more tree/graph functions, and everybody installs it because it's so useful, which is as good as having it in core. The extension doesn't grow, but the function is found useful in all the circumstances you predict and it is absorbed into core, as a 1-function extension is kinda silly. It turns out, maybe, that it's not as generally needed as you think, and you just have a custom extension, which you start adding phorum/specific stuff to that optimizes phorum when it's present. The whole PECL thing goes doesn in flames because ISPs (still) won't install anything that's not in "core" from ./configure line.
-- Some people have a "gift" link here. Know what I want? I want you to buy a CD from some indie artist. http://cdbaby.com/browse/from/lynch Yeah, I get a buck. So?