Gabriel Dos Reis <[EMAIL PROTECTED]> writes: > On Mon, 11 Jun 2007, Stephen Wilson wrote: > > | Gabriel Dos Reis <[EMAIL PROTECTED]> writes: > | > | > On Sun, 10 Jun 2007, Stephen Wilson wrote: > | > > | > | Hello Gaby, > | > | > | > | Gabriel Dos Reis <[EMAIL PROTECTED]> writes: > | > | [...] > | > | > However, I do believe the use of arrays has inherent problems in > | > | > terms of maintaining coherence of function pointers assigned to slots. > | > | > Because the mapping from declarations order to integer has lost > important > | > | > informations (name, types, etc) of the functions being mapped. > | > | > | > | Im not sure if this is fundamental to an array. I think it is > | > | entierly possible to define vtable elements at a fixed offset which > | > | provide alternative methods of indexing. Indeed, I belive the current > | > | layout provides such a rudimentary facility of mapping export labels > | > | to arity and argument type information, but the details escape me (Its > | > | been a long time since I looked at this. I recall making notes. I > | > | need to do some digging). > | > > | > I'm not sure I agree. For the array representation, numeric integrs > | > are the key. The only information they carry is the order of > | > declaration. In a context where declarations are scatered over > | > different modules (or files), there no longer is a natural order > | > of declarations. Chaos ensures. > | > | Notice that I said the vtable could have a entry to provide > | alternative indexing strategies at a _fixed_ offset. Such an entry > | could be a hash, an assoc list, etc. The current vtables do have such > | a stucture. I belive the following mappings are currently possible > | (but this is only theory, I need to work out the details): > | > | index -> function slot > | index -> name > | name -> arity > | name -> target type > | name -> argument type(s) > | name -> index > | > | This is not a complete list. For example we could map a type > | signature to the list of exports which satisfy. > > I guess what I trying to get at is what are the benefits of those > additional indirections over simple, hash table representation.
I would imagine that the vast number of lookups would suffice with an integer index. Tiny fraction would require higher level keys. > >From all I can see, the "index" key relies on order declaration which is a > non-started. The scheme "name" key is essentiablly equivalent to using a hash > table. If an extrat indirection is required to get the type, what is he > point? This indirection could certainly be made fast, probably on par with a hash. I dont think of the integer index as having anything to do with the order of declarations. I prefer to think of the relationship as coincidental. > > | Spad vtables potentially support many types of keys for indexing, not > | just integers. > > Maybe. I'm talking of Spad and its object model representation as of today. > I'm considering ways to get supports verification and extensions without > excessive performance regression. I am talking about the representaion as of today too. But as I said, I have yet to hammer out all the details. I belive that verification and extension operations would consume only tiny fraction of lookups. The slight (if any) performance bottle-neck in the current scheme would not compinsate for the global reduction in performance which a hash representation would introduce. > | > | > I would like to suggest the idea of using hastables as opposed to > | > | > arrays to implement vtables (materialization of domains and packages). > | > | > Not only it would help tame the problem of coherence, but also move > | > | > to functionalities like "post facto extensions". > | > | > | > | Roughly, what are the keys? What do the entries look like? > | > > | > The keys would be faithfull encodings of operation names, their types > | > (and possibly their scope, in case we go with nested scopes). > | > | OK. My initial feeling is that there would be a great deal of > | overhead involved in computing the hashes for such keys. > > If you use strings as encoding (traditional technique), then what you really > put in the hastable is the symbol whose name is the encoding. In that case, > the "intern" operation is done by the compiler, NOT at runtime, and look > up is quite fast. Well, intern happens at runtime quite often, but thats not the point. Im surprised that you would want to use strings. They are not as easily manipulated as, say, a struct or sexpression representation. Considering that your concerned about such high level operations such as extension, I would have thought a more malable representation would be critical. If you are constantly converting from, say, a struct representation to the corresponding string, you may just as well use the struct itself and a custom hash to index the table. > | Caching > | would help but would that not provide an opportunity for coherence > | problems to arise? > > More specificaly? Im just following the general notion that cached data can become out of sync. Its dependent on the implementation. I would trust that any solution you propose would not suffer in that regard. > [...] > > | > | I would need a clear picture of what the semantics would be for "post > | > | facto extensions". Do you sugest following Aldor explicitly? IIRC new > | > | exports introduced by `extend' are not visible to previous > | > | definitions, except via `has' predicates which execute during > | > | runtime. Are there other issues involved? > | > > | > If you do static resolution of names (which I believe we should retain), > | > then "future" dos not interfer with "past". > | > | I think I understand your statement, but not how it connects. `has' > | is (in part) an introspective runtime operation. > > There are two stages operations: static resolution of (function) names, > and dynamic resolution of the residual. Ok. So long as elimination of residual variables is dynamic, we are on the same page. > | Often the argument > | contains a free variable. I dont see how static resolution of names > | fits in this context. > > Example of cases where it won't work? No, not with the dynamic component. I read "If you do static resolution of names then future does not interfere with past" as meaning you advocated purely compile-time resolution. > The hashtable repreentation vs. array representation has no semantics effect > on well formed programs. Agreed. Thanks, Steve _______________________________________________ Axiom-developer mailing list [email protected] http://lists.nongnu.org/mailman/listinfo/axiom-developer
