Newsgroups: php.internals Path: news.php.net Xref: news.php.net php.internals:29378 Return-Path: Mailing-List: contact internals-help@lists.php.net; run by ezmlm Delivered-To: mailing list internals@lists.php.net Received: (qmail 74335 invoked by uid 1010); 9 May 2007 17:20:33 -0000 Delivered-To: ezmlm-scan-internals@lists.php.net Delivered-To: ezmlm-internals@lists.php.net Received: (qmail 74320 invoked from network); 9 May 2007 17:20:33 -0000 Received: from unknown (HELO lists.php.net) (127.0.0.1) by localhost with SMTP; 9 May 2007 17:20:33 -0000 Authentication-Results: pb1.pair.com smtp.mail=maurice@phorum.org; spf=fail; sender-id=fail Authentication-Results: pb1.pair.com header.from=maurice@phorum.org; sender-id=fail Received-SPF: fail (pb1.pair.com: domain phorum.org does not designate 217.149.192.18 as permitted sender) X-PHP-List-Original-Sender: maurice@phorum.org X-Host-Fingerprint: 217.149.192.18 smtp20.nijmegen.internl.net Solaris 10 (beta) Received: from [217.149.192.18] ([217.149.192.18:44202] helo=smtp20.nijmegen.internl.net) by pb1.pair.com (ecelerity 2.1.1.9-wez r(12769M)) with ESMTP id EE/CF-60325-FD202464 for ; Wed, 09 May 2007 13:20:33 -0400 Received: from [192.168.2.151] by smtp20.nijmegen.internl.net via 78-198.bbned.dsl.internl.net [217.149.198.78] with ESMTP id l49HKP9F024072 (8.13.8/2.04); Wed, 9 May 2007 19:20:25 +0200 (CEST) Message-ID: <464202D9.8080509@phorum.org> Date: Wed, 09 May 2007 19:20:25 +0200 Reply-To: maurice@phorum.org Organization: Phorum.org User-Agent: Thunderbird 1.5.0.10 (X11/20070403) MIME-Version: 1.0 To: Michael Walter CC: RQuadling@googlemail.com, Brian Moon , internals@lists.php.net References: <4641D92C.4050208@dealnews.com> <10845a340705090743v6aba7896y45b9f7d60a4e77ba@mail.gmail.com> <4641E3DD.8040807@phorum.org> <877e9a170705090913i320359cag81b0a3bf203e2c86@mail.gmail.com> In-Reply-To: <877e9a170705090913i320359cag81b0a3bf203e2c86@mail.gmail.com> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Subject: Re: [PHP-DEV] Tree sort in C From: maurice@phorum.org (Maurice Makaay) 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