I've never measured carefully enough to be sure that it's better to put the cost in `list?` instead of `cons`, but my guess is that the cost is better in `list?`.
There's an `unsafe-cons-list` function sets the is-a-list bit when creating a pair. That is, it always sets the bit without a test on the second argument. Some function, such as `list`, internally use `unsafe-cons-list`, since the pairs that the function creates always form a list. In some limited cases, the compiler effectively replaces `cons` with `unsafe-cons-list` to set the bit early where no run-time test is needed. Currently, `make-list` does not use `unsafe-cons-list` and the compiler is not smart enough to replace its `cons` with `unsafe-cons-list`. At Sat, 8 Mar 2014 12:53:06 -0500, Matthias Felleisen wrote: > > 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 <matth...@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 > > > > > > ____________________ > Racket Users list: > http://lists.racket-lang.org/users ____________________ Racket Users list: http://lists.racket-lang.org/users
