From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <garrigue@math.nagoya-u.ac.jp>
X-Spam-Checker-Version: SpamAssassin 3.1.3 (2006-06-01) on yquem.inria.fr
X-Spam-Level: 
X-Spam-Status: No, score=0.4 required=5.0 tests=AWL,DNS_FROM_RFC_ABUSE 
	autolearn=disabled version=3.1.3
X-Original-To: caml-list@yquem.inria.fr
Delivered-To: caml-list@yquem.inria.fr
Received: from mail4-relais-sop.national.inria.fr (mail4-relais-sop.national.inria.fr [192.134.164.105])
	by yquem.inria.fr (Postfix) with ESMTP id E503BBBAF
	for <caml-list@yquem.inria.fr>; Mon, 10 Aug 2009 04:00:59 +0200 (CEST)
X-IronPort-Anti-Spam-Filtered: true
X-IronPort-Anti-Spam-Result: ApoEAMIbf0qCNhAB/2dsb2JhbADMPIQYBQ
X-IronPort-AV: E=Sophos;i="4.43,350,1246831200"; 
   d="scan'208";a="44505823"
Received: from kurims.kurims.kyoto-u.ac.jp ([130.54.16.1])
  by mail4-smtp-sop.national.inria.fr with ESMTP/TLS/DHE-RSA-AES256-SHA; 10 Aug 2009 04:00:58 +0200
Received: from localhost (orion [130.54.16.5])
	by kurims.kurims.kyoto-u.ac.jp (8.13.8/8.13.8) with ESMTP id n7A20nbM010030;
	Mon, 10 Aug 2009 11:00:50 +0900 (JST)
Date: Mon, 10 Aug 2009 10:59:50 +0900 (JST)
Message-Id: <20090810.105950.42868244.garrigue@math.nagoya-u.ac.jp>
To: rixed@happyleptic.org
Cc: caml-list@yquem.inria.fr
Subject: Re: [Caml-list] ocamlgraph predecessors
From: Jacques Garrigue <garrigue@math.nagoya-u.ac.jp>
In-Reply-To: <20090809183246.GB25629@happyleptic.org>
References: <20090809183246.GB25629@happyleptic.org>
X-Mailer: Mew version 4.2 on Emacs 22.3 / Mule 5.0 (SAKAKI)
Mime-Version: 1.0
Content-Type: Text/Plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
X-Spam: no; 0.00; node:01 functionnal:01 doubly:01 doubly:01 caml-list:01 arbitrary:02 purely:02 data:02 implemented:02 garrigue:03 garrigue:03 jacques:03 jacques:03 languages:03 overhead:04 

From: rixed@happyleptic.org
> > What you're asking is similar to the problem of finding the predecessor
> > of an arbitrary node in a singly-linked-list.  You have no option but to
> > scan the whole list to find its predecessor.  If you had a
> > doubly-linked-list, predecessor lookups would work easily, but that's a
> > different data structure, with much more overhead.
> 
> Much more overhead, really ?
> So this is for performance reasons that all functionnal languages
> promote singly-linked lists, while for instance in Linux every list
> is implemented with a doubly linked list for purely ideological reasons ?
> 
> :-)

Yes indeed, much more overhead. But the source is not the fact you
have to maintain backlinks, but their impact on the GC.
With a GC, any modification on existing values has a cost, since you
have to keep track of them independently of the value itself.
Since linux has no GC, using doubly linked lists has only a very
limited cost, mostly related to the extra space needed.
By the way, BSD uses lots of singly-linked lists, probably because it
comes from a time when there was not so much memory.

Jacques Garrigue