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

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/ac4e4ec1/attachment.html>