XPost: comp.lang.functional   
   From: phr-2007@nightsong.com   
      
   Suppose you build a big list of cons cells, say a billion of them   
   (you're on a large machine).  This is in a runtime with traditional   
   marking or copying gc, no generation scavenging or region inference or   
   anything like that.  The collector runs every N bytes of allocation   
   for some fixed N.  Yes I know that's a dumb way to write an allocator   
   for a big-system implementation but it's fairly common for small ones.   
      
   It seems to me that the running time to allocate N cells is O(N**2)   
   because you run the collector O(N) times during the allocation, and   
   each collection costs O(N) on average.   
      
   I never realized this before.  Is it a well-known phenemonon?  Is the   
   main answer something like generation scavenging?   
      
   This relates to a real situation that came up on comp.lang.python   
   yesterday.   
      
   --- SoupGate-Win32 v1.05   
    * Origin: you cannot sedate... all the things you hate (1:229/2)