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  
 
 [ 3 post ] 

 Relevant Pages 

1. How Google Grows...and Grows...and Grows

2. no vector = vector*vector in BLAS?

3. creation instruction vs. creation expression

4. Accessing creation-time AND evaluate-time data

5. Vector set!, void vector problem

6. matrix as vector of vectors

7. Inserting a vector slice into another vector

8. Optimal SSE code for dot producting 4 vectors with another vector for the Athlon

9. (simple-vector 20) vs (vector single-float 20)

10. Vectors and Vector Spaces in ST80

11. BLT Vector problem?

12. accessing BLT vectors from C

 

 
Powered by phpBB® Forum Software