[self-interest] lookup table creation (was: reflection)

[James McCartney]

On Tuesday, November 12, 2002, at 02:32  PM, Jecel Assumpcao Jr wrote:

> On Tuesday 12 November 2002 19:02, James McCartney wrote:
>> That is interesting, because they say that in the majority of cases
>> that the table creation time was less than 1/100 of a second. For my
>> own work, music, even a pause of several milliseconds is too long,
>> but this alg. might be fast enough.
>
> You need to create the table only when first reading in the system into
> an "empty world". You probably won't be playing music just then.

Well that is what I am doing now. However I would like to have a system 
where new types and slots can be added dynamically while I *am* playing 
music. That is what I am looking for. The only solution that is truly 
incremental so far seems to be hashing.

>
> An option would be to throw away the table and build a new one every
> time the programmer makes any changes, and with this system even this
> would be fast enough. If you just patch the tables then the pause will
> be far shorter.

I'm already using row displacement dispatch tables which can do this. I 
just cannot do it while playing.

>
>> I'm looking for constant time
>> lookup and incremental update of inheritance. They say that they
>> sacrifice constant time lookup with this scheme. I'll have to read
>> the paper now..
>
> They have a small binary search. In Self we have a linear search in the
> PICs (polymorphic inline caches) so we don't have constant lookup times
> either. In fact, no processor with caches will ever really have
> constant lookup times.

A memory cache miss is still O(1) time, just larger constant factor. 
But a polymorphic cache miss is not O(1) because you then have to do an 
actual lookup which is not O(1).

-- 
--- james mccartney   james at audiosynth.com   <http://www.audiosynth.com>
SuperCollider - a real time synthesis programming language for the 
PowerMac.
<ftp://www.audiosynth.com/pub/updates/SC2.2.16.sea.hqx>