Menu

#381 TIP#225: O(1) space [range] command.

TIP Implementation
open
5
2014-08-21
2004-10-23
No

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.

Discussion

1 2 > >> (Page 1 of 2)
  • Salvatore Sanfilippo

    patch version 23Oct2004

     
  • miguel sofer

    miguel sofer - 2004-10-23
    • assigned_to: nijtmans --> msofer
     
  • miguel sofer

    miguel sofer - 2004-10-23

    Logged In: YES
    user_id=148712

    Assigning to myself

     
  • miguel sofer

    miguel sofer - 2004-10-23

    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 ...

     
  • Salvatore Sanfilippo

    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.

     
  • Salvatore Sanfilippo

    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.

     
  • Salvatore Sanfilippo

    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.

     
  • Salvatore Sanfilippo

    24Oct2004 O(1) range patch.

     
  • miguel sofer

    miguel sofer - 2004-10-24
     
  • miguel sofer

    miguel sofer - 2004-10-24

    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

     
  • Salvatore Sanfilippo

    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.

     
  • Salvatore Sanfilippo

    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.

     
  • miguel sofer

    miguel sofer - 2004-10-24

    Logged In: YES
    user_id=148712

    I'm not sure I agree. The change should definitely be
    documented, but:

    As every other Tcl_List* function converts to listType, this
    can only impact on code that mucks directly with listObj
    internals and doesn't call Tcl_ListObjGetElements() first.
    Anybody doing that should RTFM and RTFS very carefully. For
    code that uses the public APIs, everything should be safe.

     
  • Salvatore Sanfilippo

    O(1) [range] command, 25Oct2004 patch.

     
  • Salvatore Sanfilippo

    Logged In: YES
    user_id=67765

    New patch attached (range5.patch). The idea is to merge what I
    think are the best points of Miguel's and my patch,
    there are also random bugfixes.

    Description of the current structure:

    - The arithSeries object is a standalone object, there
    is no code about it in the List object metod, but
    setListFromAny knows how to convert an airthmetic
    sequence to a list without to pass for the string repr.

    - The commands lindex, llength and foreach knows about
    the arithmetic series object in order to avoid to convert
    into a list.

    - Like in the Miguel's patch, there is no longer a reference
    to a wide object inside the range, this was possible modifing
    the code in TEBC using the Miguel's implementation idea.

    - Like in Miguel's patch now there is a flag in the arithmetic
    sequence object that tells us if every element of the range
    can fit or not in an Int, or if it requires a Wide. So where
    possible the Int objects are used in place to Wide ones.

    - The patch was updated to reflect the new core changes
    just commited by Miguel. Instead of five ad-hoc checks to
    see if it's possible to update a variable directly without to
    pass for the usual API, there is now a function to test for
    this condition in a very clean way.

    - Ranges with negative step are now fixed. In general the
    algorithm that computes the length of the list is now better
    and should be definitive at this point.

    - There is now a test for the [range] command, and for
    [foreach], [lindex], [llength] in relation to the new obj type.
    Not in the patch, but attached as a different file here.

    Should be all for now.

     
  • Salvatore Sanfilippo

    Logged In: YES
    user_id=67765

    [range] test attached.

     
  • Salvatore Sanfilippo

    Logged In: YES
    user_id=67765

    [range] test attached.

     
  • Salvatore Sanfilippo

    Logged In: YES
    user_id=67765

    [range] test attached.

     
  • Salvatore Sanfilippo

    test for [range], [foreach], [lindex], [llength], arithSeriesObject-wise tests.

     
  • Donal K. Fellows

    • summary: O(1) space [range] command. --> TIP#225: O(1) space [range] command.
     
  • Salvatore Sanfilippo

    • summary: TIP#225: O(1) space [range] command. --> O(1) space [range] command.
     
  • Salvatore Sanfilippo

    Logged In: YES
    user_id=67765

    new patch that imports from the Miguel's patch the
    idea to avoid wide math when possible. The arithSeries
    object have start/end/step fields as unions now, the check
    to see if the range stores an int range or a wide one was
    already there to return the right type of Tcl object so this
    is always a win. Actually I benchmarked this patch that
    shows a non-trivial performance gain. There are not semantical
    changes in this patch, should behave the same as patch5.

     
  • Salvatore Sanfilippo

    patch version 6, 25/Oct/2004.

     
  • Salvatore Sanfilippo

    • summary: O(1) space [range] command. --> TIP#225: O(1) space [range] command.
     
  • Salvatore Sanfilippo

    Logged In: YES
    user_id=67765

    Now there is a man page for the command that is
    attached here. It's possible to view it via web at
    http://www.invece.org/rangeman.html.
    Many thanks to Andreas Kupries that found a number of
    bugs in the man page (now should be ok).

     
1 2 > >> (Page 1 of 2)