In general, it's a bad idea in Pd to write externs which create indeter- minate numbers of symbols at run time. The original intent was that the only time anyone would call gensym was on text typed by the user. In this situation the existing realization is quite adequate.
But even if you've written C code that generates millions of symbols on the fly as it runs, the (linear-time-worst-case) existing algo is no worse than the (linear-time-worst-case) "smart" algo. In real time it's always the worst case that counts, and the less variation in execution time your objects can have the less likely someone will get a bad surprise someday. So the existing routine, which is _always_ slow, is better than any algorithm that is only _occasionally_ slow.
Someday I should write more about this... as it is, I have barely got enough time to keep Pd running given all the platform changes coming down...
cheers Miller
On Fri, Sep 06, 2002 at 05:08:17PM -0400, Mathieu Bouchard wrote:
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
PD-list mailing list PD-list@iem.kug.ac.at http://iem.kug.ac.at/cgi-bin/mailman/listinfo/pd-list