[Csnd-dev] Hash Table Updated

classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|

[Csnd-dev] Hash Table Updated

Steven Yi
Hi All,

In response the reported issue with Csound's hash table reported by Eduardo, I modified the table implementation to do resizing based on load factor.  The attached test.csd performance went from ~9 seconds before change and down to 0.9 seconds after the change.  

I've pushed to code to a branch new_hash_table, visible at:


The hash table is used in various places in the code base including channels, maintaining the opcode definitions, and during parsing. The impact probably shouldn't be noticeable for small amounts of items in the table (< 6144 items), but has an impact once you go above that. There is a cost when inserting and table expansion conditions are met, but it should be worth it overall for reads/writes at the larger sizes. 

Could someone review the code?  Unit tests passed here and basic usage is working alright via live coding and Blue, but I'd like a second pair of eyes before merging.  

Thanks,
Steven


test.csd (590 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: [Csnd-dev] Hash Table Updated

moguillansky
Thanks for this. When you resize the table all cached pointers in the
channel opcodes become invalid, but there is no code checking for this.
But I did not take a look at the implementation of the hash table, so
maybe there is some other code ensuring that the pointers are still
valid after reallocation.

On 07.04.19 01:40, Steven Yi wrote:

> Hi All,
>
> In response the reported issue with Csound's hash table reported by
> Eduardo, I modified the table implementation to do resizing based on
> load factor.  The attached test.csd performance went from ~9 seconds
> before change and down to 0.9 seconds after the change.
>
> I've pushed to code to a branch new_hash_table, visible at:
>
> https://github.com/csound/csound/tree/new_hash_table
>
> The hash table is used in various places in the code base including
> channels, maintaining the opcode definitions, and during parsing. The
> impact probably shouldn't be noticeable for small amounts of items in
> the table (< 6144 items), but has an impact once you go above that.
> There is a cost when inserting and table expansion conditions are met,
> but it should be worth it overall for reads/writes at the larger sizes.
>
> Could someone review the code?  Unit tests passed here and basic usage
> is working alright via live coding and Blue, but I'd like a second
> pair of eyes before merging.
>
> Thanks,
> Steven
>
Reply | Threaded
Open this post in threaded view
|

Re: [Csnd-dev] Hash Table Updated

Steven Yi
I don't see how channel pointers become invalid. Their addresses are stored as the value pointer in the CS_HASH_TABLE_ITEM's which are transferred from the old table to the newly resized one.  

This updated test.csd does assigns an incrementing value for each channel created. It does a second pass to read the values and print it out. The correct values are printed for each channel. 



On Sat, Apr 6, 2019 at 8:30 PM Eduardo Moguillansky <[hidden email]> wrote:
Thanks for this. When you resize the table all cached pointers in the
channel opcodes become invalid, but there is no code checking for this.
But I did not take a look at the implementation of the hash table, so
maybe there is some other code ensuring that the pointers are still
valid after reallocation.

On 07.04.19 01:40, Steven Yi wrote:
> Hi All,
>
> In response the reported issue with Csound's hash table reported by
> Eduardo, I modified the table implementation to do resizing based on
> load factor.  The attached test.csd performance went from ~9 seconds
> before change and down to 0.9 seconds after the change.
>
> I've pushed to code to a branch new_hash_table, visible at:
>
> https://github.com/csound/csound/tree/new_hash_table
>
> The hash table is used in various places in the code base including
> channels, maintaining the opcode definitions, and during parsing. The
> impact probably shouldn't be noticeable for small amounts of items in
> the table (< 6144 items), but has an impact once you go above that.
> There is a cost when inserting and table expansion conditions are met,
> but it should be worth it overall for reads/writes at the larger sizes.
>
> Could someone review the code?  Unit tests passed here and basic usage
> is working alright via live coding and Blue, but I'd like a second
> pair of eyes before merging.
>
> Thanks,
> Steven
>

test.csd (750 bytes) Download Attachment