[PD] bugs and question

[Miller Puckette]

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 at iem.kug.ac.at
> http://iem.kug.ac.at/cgi-bin/mailman/listinfo/pd-list