[PD] bugs and question

Mathieu Bouchard matju at sympatico.ca
Fri Sep 6 23:08:17 CEST 2002


On Fri, 6 Sep 2002, Krzysztof Czaja wrote:

>  > symbol table _flooding_. This is usually a not-nice thing to do, as it is
>  > for all practical purposes a memory leak (symbols are forever). However if
>  > that slows down PD's symbol table lookup, then that lookup function is
>  > _badly_ _implemented_ and should be rewritten.
> do you mean, that one can write a lookup function having a constant
> execution time, regardless of a symbol table size?  Could you give
> me a pointer?

Most any language implementation having some kind of symboltable and/or
dictionaries/maps implements it as a auto-resizing hashtable such that:

 * fetch is maximum O(1)
 * store of existing key is maximum O(1)
 * store of new key is maximum O(n) (on resizing)
 * resizing occurs on every O(b^n) key-count boundary (b is constant)
 * and therefore store of new key is _average_ O(1)

to my knowledge, that includes at least Ruby, Perl, and jMax3, but I would
guess all those conditions are also met by Python, Java, PHP, C++/STL, and
such.

and that excludes PureData and jMax2.

I don't know much about Judy, and sure it's fast, but you don't need Judy
at all to meet the above conditions. It might be worth it if it has more
realtime features, eg a low maximum-time-order on store-new-key.

> Mathieu Bouchard wrote:
>  >>From the jMax 2.5 source:
>  > FTS_API void fts_atom_type_register(fts_symbol_t name, fts_class_t *cl);
>  > FTS_API int fts_atom_type_lookup(fts_symbol_t name, fts_class_t **cl);
>  > I don't know why PureData does not get added something like this.
> perhaps this 'minimalistic' attitude is one of the reasons, why Pd
> is (still!) a reliable performance tool...

To be nice with you I will call that an 'opinion'.

________________________________________________________________
Mathieu Bouchard                       http://artengine.ca/matju





More information about the Pd-list mailing list