lsearch vs 'in' speeds

[Revar Desmera]

I was testing the comparative speeds of using [lsearch] versus using  
{$val in $list} to find out if an item is in a list, and I came up  
with results that I found completely unintuitive: Using [lsearch] can  
be more than twice as fast as using [in].  I'm just wondering why this  
would be?  It seems like [in] should be slightly faster, given that it  
does only one thing, while [lsearch] has to choose between -exact, -
glob, etc.  I'm guessing that [lsearch] is compiled into a token  
internally, and [in] isn't?

It would make for much clearer code if I could use [in], but given the  
performance hit, it's looking like I need to use [lsearch].  Is there  
any chance that [in] will get optimized anytime soon?

My test results and code are below: I searched for various numbers in  
a 901 item list of numbers.

        - Revar


-------------------------test results  
below--------------------------------

Search Val = 0 (first in list)
[lsearch] 0.633263 microseconds per iteration
[expr in] 0.332367 microseconds per iteration
[in]      0.334641 microseconds per iteration

Search Val = 500 (middle of list)
[lsearch] 7.032825 microseconds per iteration
[expr in] 13.284585 microseconds per iteration
[in]      13.331358 microseconds per iteration

Search Val = 900 (last in list)
[lsearch] 12.57958 microseconds per iteration
[expr in] 25.164382 microseconds per iteration
[in]      25.172105 microseconds per iteration

Search Val = 999 (not in list)
[lsearch] 12.564098 microseconds per iteration
[expr in] 25.113188 microseconds per iteration
[in]      25.211468 microseconds per iteration


-------------------------test code below--------------------------------

namespace import ::tcl::mathop::*

set l {}
for {set i 0} {$i <= 900} {incr i} {
     lappend l $i
}

set tcl_precision 15

proc ta {a l} {
     puts -nonewline stdout {[lsearch] }
     puts stdout [time {expr {[lsearch -exact $l $a] <= 0}} 1000]
}
proc tb {a l} {
     puts -nonewline stdout {[expr in] }
     puts stdout [time {expr {$a in $l}} 1000]
}
proc tc {a l} {
     puts -nonewline stdout {[in]      }
     puts stdout [time {in $a $l} 1000]
}

foreach a {0 500 900 999} {
     puts stdout "Search Val = $a"
     ta $a $l
     tb $a $l
     tc $a $l
     puts stdout ""
}




-------------------------------------------------------------------------
This SF.net email is sponsored by the 2008 JavaOne(SM) Conference
Register now and save $200. Hurry, offer ends at 11:59 p.m.,
Monday, April 7! Use priority code J8TLD2.
http://ad.doubleclick.net/clk;198757673;13503038;p?http://java.sun.com/javaone
_______________________________________________
Tcl-mac mailing list
tcl-mac@...
https://lists.sourceforge.net/lists/listinfo/tcl-mac

[Neil Madden-2]

Hi,

I get completely different results on my Intel MacBook using a fairly  
recent CVS HEAD:

Search Val = 0
[lsearch] 0.931309 microseconds per iteration
[expr in] 0.523104 microseconds per iteration
[in]      0.535964 microseconds per iteration
Search Val = 500
[lsearch] 21.926379 microseconds per iteration
[expr in] 16.446191 microseconds per iteration
[in]      16.643726 microseconds per iteration
Search Val = 900
[lsearch] 36.251643 microseconds per iteration
[expr in] 31.532473 microseconds per iteration
[in]      31.553652 microseconds per iteration
Search Val = 999
[lsearch] 37.454146 microseconds per iteration
[expr in] 31.551733 microseconds per iteration
[in]      31.893971 microseconds per iteration
% info pa
8.5.2b1

What version were you testing? It seems that "in" is indeed faster now.

-- Neil

On 6 Apr 2008, at 22:17, Revar Desmera wrote:

> I was testing the comparative speeds of using [lsearch] versus using
> {$val in $list} to find out if an item is in a list, and I came up
> with results that I found completely unintuitive: Using [lsearch] can
> be more than twice as fast as using [in].  I'm just wondering why this
> would be?  It seems like [in] should be slightly faster, given that it
> does only one thing, while [lsearch] has to choose between -exact, -
> glob, etc.  I'm guessing that [lsearch] is compiled into a token
> internally, and [in] isn't?
>
> It would make for much clearer code if I could use [in], but given the
> performance hit, it's looking like I need to use [lsearch].  Is there
> any chance that [in] will get optimized anytime soon?
>
> My test results and code are below: I searched for various numbers in
> a 901 item list of numbers.
>
> - Revar
>
>
> -------------------------test results
> below--------------------------------
>
> Search Val = 0 (first in list)
> [lsearch] 0.633263 microseconds per iteration
> [expr in] 0.332367 microseconds per iteration
> [in]      0.334641 microseconds per iteration
>
> Search Val = 500 (middle of list)
> [lsearch] 7.032825 microseconds per iteration
> [expr in] 13.284585 microseconds per iteration
> [in]      13.331358 microseconds per iteration
>
> Search Val = 900 (last in list)
> [lsearch] 12.57958 microseconds per iteration
> [expr in] 25.164382 microseconds per iteration
> [in]      25.172105 microseconds per iteration
>
> Search Val = 999 (not in list)
> [lsearch] 12.564098 microseconds per iteration
> [expr in] 25.113188 microseconds per iteration
> [in]      25.211468 microseconds per iteration
>

This message has been checked for viruses but the contents of an attachment
may still contain software viruses, which could damage your computer system:
you are advised to perform your own checks. Email communications with the
University of Nottingham may be monitored as permitted by UK legislation.


-------------------------------------------------------------------------
This SF.net email is sponsored by the 2008 JavaOne(SM) Conference
Register now and save $200. Hurry, offer ends at 11:59 p.m.,
Monday, April 7! Use priority code J8TLD2.
http://ad.doubleclick.net/clk;198757673;13503038;p?http://java.sun.com/javaone
_______________________________________________
Tcl-mac mailing list
tcl-mac@...
https://lists.sourceforge.net/lists/listinfo/tcl-mac

[Joe English-2]

Revar Desmera wrote:
?
> I was testing the comparative speeds of using [lsearch] versus using
> {$val in $list} to find out if an item is in a list, and I came up
> with results that I found completely unintuitive: [...]
>
> It would make for much clearer code if I could use [in], but given the
> performance hit, it's looking like I need to use [lsearch]. [...]

[ with worst-case performance results: ]

> Search Val = 900 (last in list)
> [lsearch] 12.57958 microseconds per iteration
> [expr in] 25.164382 microseconds per iteration
> [in]      25.172105 microseconds per iteration

> Is there any chance that [in] will get optimized anytime soon?

Dunno, but I'd suggest that if you really need to save
those 12 microseconds per iteration, you'd be better off
not using [lsearch] *or* [in], since both do a linear search.


--Joe English

-------------------------------------------------------------------------
This SF.net email is sponsored by the 2008 JavaOne(SM) Conference
Register now and save $200. Hurry, offer ends at 11:59 p.m.,
Monday, April 7! Use priority code J8TLD2.
http://ad.doubleclick.net/clk;198757673;13503038;p?http://java.sun.com/javaone
_______________________________________________
Tcl-mac mailing list
tcl-mac@...
https://lists.sourceforge.net/lists/listinfo/tcl-mac