Newsgroups: php.internals Path: news.php.net Xref: news.php.net php.internals:43356 Return-Path: Mailing-List: contact internals-help@lists.php.net; run by ezmlm Delivered-To: mailing list internals@lists.php.net Received: (qmail 39831 invoked from network); 15 Mar 2009 23:37:44 -0000 Received: from unknown (HELO lists.php.net) (127.0.0.1) by localhost with SMTP; 15 Mar 2009 23:37:44 -0000 Authentication-Results: pb1.pair.com header.from=helly@php.net; sender-id=unknown Authentication-Results: pb1.pair.com smtp.mail=helly@php.net; spf=unknown; sender-id=unknown Received-SPF: unknown (pb1.pair.com: domain php.net does not designate 85.214.94.56 as permitted sender) X-PHP-List-Original-Sender: helly@php.net X-Host-Fingerprint: 85.214.94.56 aixcept.net Linux 2.6 Received: from [85.214.94.56] ([85.214.94.56:59855] helo=h1149922.serverkompetenz.net) by pb1.pair.com (ecelerity 2.1.1.9-wez r(12769M)) with ESMTP id C2/DB-06903-8419DB94 for ; Sun, 15 Mar 2009 18:37:44 -0500 Received: from MBOERGER-ZRH.ad.corp.google.com (221-114.62-81.cust.bluewin.ch [81.62.114.221]) (using TLSv1 with cipher AES256-SHA (256/256 bits)) (No client certificate requested) by h1149922.serverkompetenz.net (Postfix) with ESMTP id 1011911F37B; Mon, 16 Mar 2009 00:37:41 +0100 (CET) Date: Mon, 16 Mar 2009 00:36:15 +0100 Reply-To: Marcus Boerger X-Priority: 3 (Normal) Message-ID: <837628007.20090316003615@marcus-boerger.de> To: Ben Smithers CC: internals@lists.php.net In-Reply-To: References: MIME-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: 8bit Subject: Re: [PHP-DEV] SplStack Implementation From: helly@php.net (Marcus Boerger) Hello Ben, there is no need in checking whether the implementation uses single or double linked. Access to any structure from the engine will always be slower by orders of magnitude, then maintaining a pinter structure directly in C code. Now doing something with that in PHP code will again be slower - by orders of magnitude. marcus Sunday, March 15, 2009, 2:19:55 PM, you wrote: > Firstly, apologies if this is not the correct place to ask such a > question - I was directed here from a forum. > I recently discovered the datastructures found in the Standard PHP > Library. I noticed that SplStack is implemented using a doubly-linked > list and wondered why. Given that a stack is LIFO store and the only > operations really needed are push and pop, why would next and previous > pointers be required on each item? There's no requirement to allow > iteration over a stack. > It would seem to me that a stack should require a linear linked list and > a pointer to the top of the stack - which would have roughly half the > memory overhead of a doubly-linked list (half the number of pointers). > Do i just have no idea what i'm talking about or have i missed something > obvious? > Thanks in advance, > Ben Best regards, Marcus