BLT vector creation: creation time grows as number of vectors created grows
Author Message
BLT vector creation: creation time grows as number of vectors created grows

I've noticed that vector creation time increases as the number of
vectors created increases. Below is a dramatic illustration. This
example was performed using BLT 2.4x with Tcl 8.3.2 on Windows NT.

% time { for {set i 0} {\$i< 2000} {incr i} {
blt::vector create #auto

Quote:
}}

4607000 microseconds per iteration
% time { for {set i 0} {\$i< 2000} {incr i} {
blt::vector create #auto
Quote:
}}

15372000 microseconds per iteration
% time { for {set i 0} {\$i< 2000} {incr i} {
blt::vector create #auto
Quote:
}}

27729000 microseconds per iteration

Could this be caused by the vector creation command doing a linear
search for the existence of the vector name? If so, maybe a hash table
of vector names could remedy this.

This latency is a real issue I'm facing where I could have over 5000
vectors being created at a given time.

Sat, 04 Sep 2004 01:18:59 GMT
BLT vector creation: creation time grows as number of vectors created grows

Quote:

> I've noticed that vector creation time increases as the number of
> vectors created increases. Below is a dramatic illustration. This
> example was performed using BLT 2.4x with Tcl 8.3.2 on Windows NT.
> % time { for {set i 0} {\$i< 2000} {incr i} {
>   blt::vector create #auto
> }}
> 4607000 microseconds per iteration
> % time { for {set i 0} {\$i< 2000} {incr i} {
>   blt::vector create #auto
> }}
> 15372000 microseconds per iteration
> % time { for {set i 0} {\$i< 2000} {incr i} {
>   blt::vector create #auto
> }}
> 27729000 microseconds per iteration
> Could this be caused by the vector creation command doing a linear
> search for the existence of the vector name? If so, maybe a hash table
> of vector names could remedy this.
> This latency is a real issue I'm facing where I could have over 5000
> vectors being created at a given time.

Your diagnosis is exactly right.  There's a lot of (redundant)
checking going on for a unique vector name.  I've fixed this
so that vector generation appears linear.

% time { for {set i 0} {\$i< 2000} {incr i} {
blt::vector create #auto
}}

58738 microseconds per iteration
46543 microseconds per iteration
42922 microseconds per iteration
44836 microseconds per iteration
42191 microseconds per iteration
45373 microseconds per iteration
57235 microseconds per iteration
53460 microseconds per iteration
42213 microseconds per iteration
43422 microseconds per iteration
45275 microseconds per iteration
43782 microseconds per iteration
43708 microseconds per iteration
41264 microseconds per iteration

I can send you a patch if need something right away.  This bug affects
only "#auto" vector name generation.  Therefore, if you make up your
own vector name, you won't see this slowdown.

% time { for {set i 0} {\$i< 2000} {incr i} {
blt::vector create v\$i
}}
37720 microseconds per iteration
56042 microseconds per iteration
55467 microseconds per iteration
45022 microseconds per iteration
45199 microseconds per iteration
44782 microseconds per iteration
46710 microseconds per iteration
44679 microseconds per iteration
46323 microseconds per iteration
44841 microseconds per iteration
44291 microseconds per iteration

Thanks for the bug report and the diagnosis.  I really appreciate it.

--gah

Sat, 04 Sep 2004 12:50:11 GMT
BLT vector creation: creation time grows as number of vectors created grows
George,
Thanks for the fix.  I'll look forward to the patch.
Todd

Quote:

> > I've noticed that vector creation time increases as the number of
> > vectors created increases. Below is a dramatic illustration. This
> > example was performed using BLT 2.4x with Tcl 8.3.2 on Windows NT.

> > % time { for {set i 0} {\$i< 2000} {incr i} {
> >   blt::vector create #auto
> > }}
> > 4607000 microseconds per iteration
> > % time { for {set i 0} {\$i< 2000} {incr i} {
> >   blt::vector create #auto
> > }}
> > 15372000 microseconds per iteration
> > % time { for {set i 0} {\$i< 2000} {incr i} {
> >   blt::vector create #auto
> > }}
> > 27729000 microseconds per iteration

> > Could this be caused by the vector creation command doing a linear
> > search for the existence of the vector name? If so, maybe a hash table
> > of vector names could remedy this.

> > This latency is a real issue I'm facing where I could have over 5000
> > vectors being created at a given time.

> Your diagnosis is exactly right.  There's a lot of (redundant)
> checking going on for a unique vector name.  I've fixed this
> so that vector generation appears linear.

>     % time { for {set i 0} {\$i< 2000} {incr i} {
>        blt::vector create #auto
>     }}

>     58738 microseconds per iteration
>     46543 microseconds per iteration
>     42922 microseconds per iteration
>     44836 microseconds per iteration
>     42191 microseconds per iteration
>     45373 microseconds per iteration
>     57235 microseconds per iteration
>     53460 microseconds per iteration
>     42213 microseconds per iteration
>     43422 microseconds per iteration
>     45275 microseconds per iteration
>     43782 microseconds per iteration
>     43708 microseconds per iteration
>     41264 microseconds per iteration

> I can send you a patch if need something right away.  This bug affects
> only "#auto" vector name generation.  Therefore, if you make up your
> own vector name, you won't see this slowdown.

>     % time { for {set i 0} {\$i< 2000} {incr i} {
>   blt::vector create v\$i
>     }}
>     37720 microseconds per iteration
>     56042 microseconds per iteration
>     55467 microseconds per iteration
>     45022 microseconds per iteration
>     45199 microseconds per iteration
>     44782 microseconds per iteration
>     46710 microseconds per iteration
>     44679 microseconds per iteration
>     46323 microseconds per iteration
>     44841 microseconds per iteration
>     44291 microseconds per iteration

> Thanks for the bug report and the diagnosis.  I really appreciate it.

> --gah

Sun, 05 Sep 2004 01:48:17 GMT

 Page 1 of 1 [ 3 post ]

Relevant Pages