Patches item #1472443, was opened at 2006-04-18 11:19
Message generated for change (Comment added) made by jepler
You can respond by visiting: 
https://sourceforge.net/tracker/?func=detail&atid=312883&aid=1472443&group_id=12883

Please note that this message will contain a full copy of the comment thread,
including the initial issue submission, for this request,
not just the latest update.
Category: bwidget
Group: None
Status: Open
Resolution: None
Priority: 5
Submitted By: Jeff Epler (jepler)
Assigned to: Jeffrey Hobbs (hobbs)
Summary: fix for several causes of ListBox slowness

Initial Comment:
The bwidget 1.7 ListBox has several pieces of code that
lead to O(N**2) time to insert N items into a new
ListBox, and then display them (execute 'update')

I made the following timings before and after my patch:

#items time (ms)  ms/item
  4000     5842    1.460
  8000    24053    3.007
 16000    90522    5.658
 
  4000     1303    0.326
  8000     2599    0.325
 16000     5304    0.332

For 16000 items, the speedup is about 17x.  Because
ms/item is nearly constant for different item counts,
the performance is probably O(N).

This patch is against the 1.7 ListBox, but before
submitting I tested with the CVS version of listbox.tcl
and found that the N-squared performance problem still
exists.  I believe this patch is "of interest" even if
it doesn't automatically apply.

----------------------------------------------------------------------

> Comment By: Jeff Epler (jepler)
Date: 2006-04-18 11:23

Message:
Logged In: YES 
user_id=2772

I'm using bwidget with tcl/tk8.4.10.  There are still
N-squared behaviors with "-selectfill 1".

----------------------------------------------------------------------

You can respond by visiting: 
https://sourceforge.net/tracker/?func=detail&atid=312883&aid=1472443&group_id=12883


-------------------------------------------------------
This SF.Net email is sponsored by xPML, a groundbreaking scripting language
that extends applications into web and mobile media. Attend the live webcast
and join the prime developer group breaking into this new coding territory!
http://sel.as-us.falkag.net/sel?cmd=lnk&kid=110944&bid=241720&dat=121642
_______________________________________________
Tcllib-bugs mailing list
Tcllib-bugs@[...].net
https://lists.sourceforge.net/lists/listinfo/tcllib-bugs