Hi All,

I was running into a problem where an older project of mine was taking
an extremely long time to parse.  Upon investigation, I discovered
there was some highly inefficient code for the CS_VAR_POOL's that was
causing extreme slow down when there were a large number of variables.
 The analysis is as follows:

* When I first worked on the type system work for CS6, I had used only
a linked-list for variables in the var pool. This worked well to get
going, but this was highly inefficient for two things: searching for a
var by name, as well as insertion at tail.  Both required walking the
linked list which is horribly slow.

* At the time, I was reworking alot of code from CS5.  CS5 used a hash
table for variable tracking so it was fast, as well as a linked list
(I think).  The code however was not very clear to me at the time.

* Also, this initial work was done before I had abstracted out the
reusable CS_HASH_TABLE structure and functions.


With the above, I reworked the CS_VAR_POOL code as follows:

* Added a ->table member that is a CS_HASH_TABLE.  Now when variables
are added, it is added both to the linked-list as well as entered into
the hash table.

* The csoundFindVariableWithName() now only uses the hash table to
search for variables. This improved the speed a lot.

* However, the project still had a small pause. This turned out to be
due to insertion of new vars and walking the list.  I added a ->tail
member to the CS_VAR_POOL so that insertions to the tail could happen
very quickly. The result is that the project parse time went from >15
seconds to almost instantly.

Please let me know if you have any issues after this commit.  So far
the projects I've tested seem to have a noticeable parse time
improvement and I have not had any crashes. ("make csdtests" seems to
run more quickly too.)  I only wish I had caught this earlier!

Thanks!
steven

------------------------------------------------------------------------------
_______________________________________________
Csound-devel mailing list
Csound-devel@lists.sourceforge.net

Nice one Steven. Can't say I noticed, but I'm sure I would have eventually ;)

On 5 April 2014 17:25, Steven Yi  wrote:
> Hi All,
>
> I was running into a problem where an older project of mine was taking
> an extremely long time to parse.  Upon investigation, I discovered
> there was some highly inefficient code for the CS_VAR_POOL's that was
> causing extreme slow down when there were a large number of variables.
>  The analysis is as follows:
>
> * When I first worked on the type system work for CS6, I had used only
> a linked-list for variables in the var pool. This worked well to get
> going, but this was highly inefficient for two things: searching for a
> var by name, as well as insertion at tail.  Both required walking the
> linked list which is horribly slow.
>
> * At the time, I was reworking alot of code from CS5.  CS5 used a hash
> table for variable tracking so it was fast, as well as a linked list
> (I think).  The code however was not very clear to me at the time.
>
> * Also, this initial work was done before I had abstracted out the
> reusable CS_HASH_TABLE structure and functions.
>
>
> With the above, I reworked the CS_VAR_POOL code as follows:
>
> * Added a ->table member that is a CS_HASH_TABLE.  Now when variables
> are added, it is added both to the linked-list as well as entered into
> the hash table.
>
> * The csoundFindVariableWithName() now only uses the hash table to
> search for variables. This improved the speed a lot.
>
> * However, the project still had a small pause. This turned out to be
> due to insertion of new vars and walking the list.  I added a ->tail
> member to the CS_VAR_POOL so that insertions to the tail could happen
> very quickly. The result is that the project parse time went from >15
> seconds to almost instantly.
>
> Please let me know if you have any issues after this commit.  So far
> the projects I've tested seem to have a noticeable parse time
> improvement and I have not had any crashes. ("make csdtests" seems to
> run more quickly too.)  I only wish I had caught this earlier!
>
> Thanks!
> steven
>
> ------------------------------------------------------------------------------
> _______________________________________________
> Csound-devel mailing list
> Csound-devel@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/csound-devel

------------------------------------------------------------------------------
_______________________________________________
Csound-devel mailing list
Csound-devel@lists.sourceforge.net