View Ticket
Not logged in
2017-02-12
11:43
add some tests for singleton list optimisation [738900] Leaf check-in: ac115634a0 user: aspect tags: aspect-shimmer-singleton-lists
2017-02-11
07:21
Apply ferrieux' shimmer-alex.patch from ticket [738900] check-in: a238a2fafc user: aspect tags: aspect-shimmer-singleton-lists
2016-08-20
03:18 Ticket [738900ffff] limit shimmer of singleton lists status still Open with 3 other changes artifact: f011afb84b user: aspect
2016-08-19
21:35 Add attachment shimmer-alex.patch to ticket [738900ffff] artifact: 597bf65e91 user: ferrieux
21:25 Ticket [738900ffff] limit shimmer of singleton lists status still Open with 3 other changes artifact: 759a3e7deb user: ferrieux
17:18 Ticket [738900ffff]: 3 changes artifact: b539eb8383 user: ferrieux
17:12 Ticket [738900ffff]: 3 changes artifact: 839f620292 user: ferrieux
13:17 Ticket [738900ffff]: 6 changes artifact: d5c3ef48f9 user: aspect
13:10 Add attachment aspect-singleton-list-738900.patch to ticket [738900ffff] artifact: a4d9149d24 user: aspect
2007-04-25
05:35 Ticket [738900ffff] limit shimmer of singleton lists status still Open with 6 other changes artifact: 371816b1ec user: msofer
02:21 Open ticket [738900ffff]. artifact: 1d212915a9 user: hobbs
2007-04-21
04:35 Add attachment listDiff2 to ticket [738900ffff] artifact: d8f5ea0db9 user: msofer
04:35 Closed ticket [738900ffff]: limit shimmer of singleton lists plus 8 other changes artifact: 9018ff4645 user: msofer
02:50 Ticket [738900ffff]: 4 changes artifact: b16ba505ad user: msofer
02:50 Add attachment listDiff to ticket [738900ffff] artifact: c40540380e user: msofer
00:52 Ticket [738900ffff] limit shimmer of singleton lists status still Open with 5 other changes artifact: 0fb073a421 user: msofer
2007-04-20
12:03 Ticket [738900ffff]: 5 changes artifact: 97fa100ddd user: kennykb
2003-05-17
01:13 Add attachment shimmer.patch to ticket [738900ffff] artifact: 7a89b7a00e user: dgp
01:13 Ticket [738900ffff] limit shimmer of singleton lists status still Open with 4 other changes artifact: bde9e714eb user: dgp
2003-05-16
18:13 New ticket [738900ffff]. artifact: 3d0a150fd2 user: dgp

Ticket UUID: 738900
Title: limit shimmer of singleton lists
Type: Patch Version: None
Submitter: dgp Created on: 2003-05-16 18:13:44
Subsystem: 14. List Object Assigned To: msofer
Priority: 5 Medium Severity: Minor
Status: Open Last Modified: 2016-08-20 03:18:14
Resolution: Postponed Closed By: nobody
    Closed on: 2007-04-20 21:35:55
Description:
If a Tcl_Obj is a single value, we lose it's intrep
when converting to the "list" objType.

We can avoid loss of intrep by just making the
object into the first element of the objPtr
array of the List struct, so long as we're careful
about string reps that would be broken into
multiple elements.

Here's a patch that almost works.  It makes
test append-4.8 fail.  Comments?
User Comments: aspect added on 2016-08-20 03:18:14:
Well spotted with the stringrep problem - your patch looks good to me and I like DupShaved; that will likely prove useful for other related micro-optimisations.

When I get some more time I'll try to come up with some suitable tests - hopefully I've contacted Andreas correctly and will be able to put these on a branch that's a little bit easier to integrate than random patchsets.

fwiw, my timezone is utc+10

ferrieux added on 2016-08-19 21:25:26:
The attached patch shimmer-alex.patch avoids the pitfall by using a new "TclDupShaved" utility that duplicates an object (with an intrep) *without* carrying along its strep. That's faster than first duplicating, then freeing the strep.

Output with trunk: A1.31.3B
Output with patch: A1.31.3B

As you can see, EIAS is back :P

% tcl::unsupported::representation $x
value is a list with a refcount of 4, object pointer at 0x13cdfb0, internal representation 0x13f7b50:(nil), string representation "   1.3   "
% tcl::unsupported::representation [lindex $x 0]
value is a double with a refcount of 2, object pointer at 0x13d0200, internal representation 0x3ff4cccccccccccd:0x13ce040, string representation "1.3"

ferrieux added on 2016-08-19 17:18:07:
TYPO ALERT!!!

Wherever I wrote "intrep" in the previous comment, of course I meant "strep" (string representation)...
Sorry...

ferrieux added on 2016-08-19 17:12:23:
To verify, you can simply parse [::tcl::unsupported::representation]'s output on typical shimmering paths. Sure, that's exactly what we try to discourage, but who reads the test suite ? ;-)


Now looking at the current implementation, there's still a problem with canonicity, and I believe that may be the reason for the ill-understood breakage mentioned earlier:  beware of any existing string rep for the incoming number !

Demo script:

set x "   1.3   ";expr {log($x)};llength $x;puts A[lindex $x 0][lindex $x 0]B

Output with trunk: A1.31.3B
Output with patch: A   1.3      1.3   B

As you can see, the problem is that you keep the intrep (possibly noncanonical, e.g. with extra space) of the incoming number both for the "boxed" number and the list:

% tcl::unsupported::representation $x
value is a list with a refcount of 6, object pointer at 0x1c325d0, internal representation 0x1c411d0:(nil), string representation "   1.3   "
% tcl::unsupported::representation [lindex $x 0]
value is a double with a refcount of 2, object pointer at 0x1c366e0, internal representation 0x3ff4cccccccccccd:(nil), string representation "   1.3   "

While I think only the list (the toplevel object that we are delicately shimmering) should keep that intrep (and be sure to set isCanonical to FALSE), and the boxed number should have no string rep.

aspect added on 2016-08-19 13:17:17:
Attached aspect-singleton-list-738900.patch which is against trunk [632e9e93f1].  This handles numeric types and tclEndOffsetType and doesn't cause any new test failures in Tcl.  I have some failures in the Tk test suite, but none of those mentioned below - they seem to be related to my desktop/wm/fonts.

Not sure what test cases should be added to verify this patch?

There's probably some synergy between this and branch [pyk-emptystring] which could be exploited.

msofer added on 2007-04-25 05:35:29:
Logged In: YES 
user_id=148712
Originator: NO

* generic/tclListObj.c: reverting [Patch 738900] (committed on
2007-04-20). Causes some Tk test breakage of unknown importance,
but the impact of the patch itself is likely to be so small that
it does not warrant investigation at this time.

hobbs added on 2007-04-25 02:21:57:
Logged In: YES 
user_id=72656
Originator: NO

This patch causes Tk's border-1.1, bitmap-1.1 and cursor-1.1 to fail.

msofer added on 2007-04-21 04:35:55:

File Added - 225892: listDiff2

Logged In: YES 
user_id=148712
Originator: NO

Mystery solved: a string that contains backslashes or braces needs full parsing. Updated patch, committed.
File Added: listDiff2

msofer added on 2007-04-21 02:50:28:

File Deleted - 225855: 



File Added - 225875: listDiff

Logged In: YES 
user_id=148712
Originator: NO

New patch after first comments
File Added: listDiff

msofer added on 2007-04-21 00:52:59:

File Added - 225855: listDiff

Logged In: YES 
user_id=148712
Originator: NO

Attached a current patch with three shortcuts:
 - it avoids most work for empty strings
 - it avoids computing the string rep for numbers
 - it avoids losing the internal rep for singletons that do not have a string rep

I am a bit mystified as to why the qualification about not having a string rep is necessary; without it, failures at: append-4.8, appendComp-4.8, opt-[3.1/3.2/5.1], safe-7.2
 
File Added: listDiff

kennykb added on 2007-04-20 12:03:38:
Logged In: YES 
user_id=99768
Originator: NO

Is this still an issue after so long? (I know that you have been in the code a good bit more recently than I have.)  

Don's patch no longer applies.

Avoiding shimmer of singletons sounds like a good idea, if we can make it go.

dgp added on 2003-05-17 01:13:44:

File Added - 50519: shimmer.patch

Attachments:

  • shimmer-alex.patch [download] added by ferrieux on 2016-08-19 21:35:42. [details]
  • aspect-singleton-list-738900.patch [download] added by aspect on 2016-08-19 13:10:47. [details]
  • listDiff2 [download] added by msofer on 2007-04-21 04:35:55. [details]
  • listDiff [download] added by msofer on 2007-04-21 02:50:28. [details]
  • shimmer.patch [download] added by dgp on 2003-05-17 01:13:44. [details]