From: SourceForge.net <no...@so...> - 2004-10-24 15:13:48
|
Patches item #1052584, was opened at 2004-10-23 01:22 Message generated for change (Comment added) made by antirez You can respond by visiting: https://sourceforge.net/tracker/?func=detail&atid=310894&aid=1052584&group_id=10894 Category: 14. List Object Group: TIP Implementation Status: Open Resolution: None Priority: 5 Submitted By: Salvatore Sanfilippo (antirez) Assigned to: miguel sofer (msofer) Summary: O(1) space [range] command. Initial Comment: That's a first version of the [range] command working in O(1) space. There is some minor bug I'll fix tomorrow, but the basic stuff appears to be ok. commands aware of the new arithSeries object in the TEBC and normal fashion: llength lindex foreach New commands: Only [range]. The change is minimal from the user point of view. From the core side is a bit more tricky because of the O(1) space aims. Other stuff optimized for this object: SetListObjFromAny will directly convert ranges into lists without to pass for the string repr. Open issues: The code needs a check in order to don't allow the generation of ranges that are longer than the max listObj length supported by the current Tcl code. For the rest, I used Wide Ints in order to ensure that ranges shorter than the max list length, but having as elements Wide ints will work. Performance changes: The effects on the performances of the list-oriented should be very small, there is some test more than before. The case of: foreach x [range 0 $n] is faster than the equivalent [for] form by 10% to 30% from a first test. The appended patch should apply against HEAD. ---------------------------------------------------------------------- >Comment By: Salvatore Sanfilippo (antirez) Date: 2004-10-24 15:13 Message: Logged In: YES user_id=67765 Just another comment, I readed the patch carefully and noticed something that may create problems. Some code may assume that for instance calling Tcl_ListObjLength() will always convert an object to the List type, and then access its internal representation. With Miguel's patch this is no longer true, and this may create problems, so maybe to avoid to put the range's stuff inside the List's type methods can be a good idea. ---------------------------------------------------------------------- Comment By: Salvatore Sanfilippo (antirez) Date: 2004-10-24 14:50 Message: Logged In: YES user_id=67765 I just read Miguel's patch. Very great! A lot of issues resolved, this patch is better in every way and resolves some bad thing of my patch, notably that the object needed to take a reference to a wide object. Thanks for the good work. ---------------------------------------------------------------------- Comment By: miguel sofer (msofer) Date: 2004-10-24 13:50 Message: Logged In: YES user_id=148712 Alternative implementation attached (msrange.patch), for discussion. It is based heavily on antirez's patch. The main differences are: - the new arithSeriesType are not meant to be exposed to the user; they are used internally as optimisations by some list commands (foreach, llength, lindex; lrange could be added), with automatic conversion to list type for the others. There are no special commands for handling the new types. - the new obj types do not store Tcl_Objs, but ints or wideInts according to necessity. These are stored in a union (alternatively one could consider having two different types for ints and wides). - no new commands are meant to be exposed; this patch does not touch the stubs tables ---------------------------------------------------------------------- Comment By: Salvatore Sanfilippo (antirez) Date: 2004-10-24 09:34 Message: Logged In: YES user_id=67765 This new patch fixes two problems: the cached object string representation now is invalidated in the TEBC code, and there is a check to be sure the cached object is still of the wide int, otherwise a new object is created. ---------------------------------------------------------------------- Comment By: Salvatore Sanfilippo (antirez) Date: 2004-10-24 09:34 Message: Logged In: YES user_id=67765 This new patch fixes two problems: the cached object string representation now is invalidated in the TEBC code, and there is a check to be sure the cached object is still of the wide int, otherwise a new object is created. ---------------------------------------------------------------------- Comment By: Salvatore Sanfilippo (antirez) Date: 2004-10-23 19:07 Message: Logged In: YES user_id=67765 This is a new version of the patch. changes: Dup method more sane semantically, should be the same in the pratice but now the cached object is copied exactly. A very important fix in the TEBC about I bug I introduced with may changes, thanks to Miguel for discovering it. Fixed detection of infinite ranges. Ranges with more elements than the max list length now reports an error like [lrepeat] does. ---------------------------------------------------------------------- Comment By: miguel sofer (msofer) Date: 2004-10-23 15:27 Message: Logged In: YES user_id=148712 The patch uses wideInts for {start,end, step}, but is restricted to a length of INTMAX elements - not this patch's fault, Tcl lists have this restriction. One possible performance impact is that the element variable in [foreach] loops is always a wideInt. Whenever the element is representable by an int, this may impose conversion costs in further computations with it. It may be interesting to study how to return an int object whenever possible. Mybe adding a arithSeriesRepPtr->intObjPtr, and insuring that one of those pointers is always valid, and the other is NULL? There may be better solutions ... ---------------------------------------------------------------------- Comment By: miguel sofer (msofer) Date: 2004-10-23 10:12 Message: Logged In: YES user_id=148712 Assigning to myself ---------------------------------------------------------------------- You can respond by visiting: https://sourceforge.net/tracker/?func=detail&atid=310894&aid=1052584&group_id=10894 |