[racket] first vs car ; last vs cdr ; empty? vs null?

From: Matthias Felleisen (matthias at ccs.neu.edu)
Date: Sat Mar 8 12:53:06 EST 2014

I sit corrected :-) (I had it right at some point)


On Mar 8, 2014, at 12:52 PM, Carl Eastlund wrote:

> If every cons set those bits, it would still take constant time because you'd only have to look one deep.  However, the important part is that currently cons never has to inspect its arguments.  Given that cons may be called frequently in a program that never uses list?, one does not want to pay for inspecting those arguments until needed.
> 
> Carl Eastlund
> 
> 
> On Sat, Mar 8, 2014 at 12:47 PM, Matthias Felleisen <matthias at ccs.neu.edu> wrote:
> 
> You want cons (the frequent action) to take constant time: allocate pointer, set two fields.
> 
> 
> On Mar 8, 2014, at 12:33 PM, David T. Pierson wrote:
> 
> > On Fri, Mar 07, 2014 at 11:03:57PM -0500, Carl Eastlund wrote:
> >> The first/rest operations do not use a memoization table.  They test using
> >> the list? primitive, which is built in and actually has a couple of tag
> >> bits reserved on every cons object for memoizing its results.  So the
> >> operation really is quite fast.
> >
> > I take this to mean there is a bit in the cons object for storing
> > whether it is a list, and that this bit is set via `list?'.
> >
> > Why wouldn't the bit be set via `cons'?
> >
> > Also, when I do:
> >
> >  $ racket
> >  Welcome to Racket v6.0.0.2.
> >> (let ((ls (make-list 50000000 0)))
> >    (time (list? ls))
> >    (time (list? ls))
> >    (time (list? ls))
> >    (time (list? ls))
> >    (time (list? ls)))
> >
> >  cpu time: 220 real time: 220 gc time: 0
> >  cpu time: 112 real time: 112 gc time: 0
> >  cpu time: 60 real time: 58 gc time: 0
> >  cpu time: 28 real time: 29 gc time: 0
> >  cpu time: 16 real time: 15 gc time: 0
> >  #t
> >
> > Why does the time decrease gradually, rather than the 2nd and subsequent
> > times being roughly equivalent?
> >
> > Thanks.
> >
> > David
> > ____________________
> >  Racket Users list:
> >  http://lists.racket-lang.org/users
> 
> 
> ____________________
>   Racket Users list:
>   http://lists.racket-lang.org/users
> 
> 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20140308/b0c8cc9f/attachment-0001.html>

Posted on the users mailing list.