Cache line list handling
|
From: MitchAlsup on 15 Jul 2010 15:31 On Jul 15, 11:05 am, jacko <jackokr...(a)gmail.com> wrote: > On Jul 14, 5:59 pm, MitchAlsup <MitchAl...(a)aol.com> wrote: > > > > > > > On Jul 14, 5:37 am, "Piotr Wyderski" > > > <piotr.wyder...(a)mothers.against.spam.gmail.com> wrote: > > > Not only, Sparcs have much worse memory disambiguation mechanisms. > > > Even such a simple loop shows stunning differences: > > > > for(volatile unsigned int i = 0; i != 1000000000; ++i); > > > > Investigation at the assembler level has shown that Sparc is good > > > (i.e. Xeon-like) at loads and stores, but when there is a long > > > store-load dependence, the performance loss is a total disaster, to > > > put it mildly. Xeons do not exhibit this kind of problems. > > > x86 grew up in an environment where stores were reloaded in a rather > > short amount of time {arguments get pushed, then accessed a couple > > cycles later in the called subroutine.) Thus, there are mechanisms to > > forward store data to loads when the addresses match even when the > > store instruction has not retired. This normally goes under the > > monicer of Store-to-Load forwarding (STLF). > > > Mitch > > Yes, a force write-thru signal? No, forward the unretired memory aligned store data to a younger executing load instruction. The data cache update remains defered until after the store retires. Mitch
From: jacko on 15 Jul 2010 15:39 On Jul 15, 7:35 pm, George Neuner <gneun...(a)comcast.net> wrote: > On Thu, 15 Jul 2010 09:09:52 -0700 (PDT), jacko <jackokr...(a)gmail.com> > wrote: > > > > > > >On Jul 15, 4:48 pm, George Neuner <gneun...(a)comcast.net> wrote: > >> On Thu, 15 Jul 2010 08:17:44 -0700 (PDT), jacko <jackokr...(a)gmail.com> > >> wrote: > > >> >Is > > >> >http://groups.google.com/group/comp.lang.forth/browse_thread/thread/4... > > >> >important for solving the GC problem? Ref FIFOO > > >> There isn't enough detail in that conversation to figure out what > >> problem the structure is trying to solve. What exactly are you > >> asking? > > >> George > > >From my own prospective the mark and sweep cache flushing garbage > >collector problem. Also related to the circular pointer counted > >reference memory leak problem, and the common tail evaluation of > >circular structures solution. > > I don't see how the "FIFOO" described in the link would help cache > pollution in GC (any GC). Since marking and copying are both > read-only (no modify) operations, the best solution is to fetch the > value(s) into the L1 cache bypassing the other levels, and for copying > or compacting GC to write it out again bypassing the other levels. I > don't know of a workable solution for sweeping which does modify > structures. Marking involves a WRITE. > Likewise, I can't see how it fixes circular linking ... all FIFOO > seems intended to do is provide a way to find the roots of structures > that share common sub-structure. I didn't see any provision to > prevent circular linking. It seems to me to be a heavy-weight > solution to the problem - in the absence of tracing or copying GC, Tail self linking becomes 'conceptually' impossible/not supported, and circular linking can be found by common tail => i.e. will be one of the heads, and so will share a common tail. So an object traversal of all heads to check not common tail ... a reduction in computation for self referencing structures, and an easy active head count = 0 test for complete free, which will keep you in list elements for quite a while before any complex gc code has to be run. FIFOO does not prevent self references, but makes it easier to computationally detect if necessary. Mark sweep involves marking the whole active list node set. Three total traversals or two if a binary bool marker is used. Allocate copy involves handles to every list node or a referer node list for back poking, and involves full traversal of the active node list and reallocation and copying of them. > ISTM that using an object table to indirectly reference objects with > multiple parents is a better solution ... delete/sweep of an object > stops where it chases a pointer into the object table. Apart from TABLE being associated with heap compaction/fragmentation issues, could you elaborate. To me it seems like any node which has more than one referrer, referers to it through a handle in the table. What of just one referrer and the extra bool? How is in table detected? How are circular references handled or avoided? (by a handle of course, but...) How is self reference handled or avoided? If I understand you it's about kind of a join node inserted transparently agregated in the table with all the other join nodes, and including a referer count and a node class indication. So that forces some kind of count and class per node rather than per structure. So more than 2 machine words per node? Cheers Jacko
From: jacko on 15 Jul 2010 15:46 On Jul 15, 7:35 pm, George Neuner <gneun...(a)comcast.net> wrote: > On Thu, 15 Jul 2010 09:09:52 -0700 (PDT), jacko <jackokr...(a)gmail.com> > wrote: > > > > > > >On Jul 15, 4:48 pm, George Neuner <gneun...(a)comcast.net> wrote: > >> On Thu, 15 Jul 2010 08:17:44 -0700 (PDT), jacko <jackokr...(a)gmail.com> > >> wrote: > > >> >Is > > >> >http://groups.google.com/group/comp.lang.forth/browse_thread/thread/4... > > >> >important for solving the GC problem? Ref FIFOO > > >> There isn't enough detail in that conversation to figure out what > >> problem the structure is trying to solve. What exactly are you > >> asking? > > >> George > > >From my own prospective the mark and sweep cache flushing garbage > >collector problem. Also related to the circular pointer counted > >reference memory leak problem, and the common tail evaluation of > >circular structures solution. > > I don't see how the "FIFOO" described in the link would help cache > pollution in GC (any GC). Since marking and copying are both > read-only (no modify) operations, the best solution is to fetch the > value(s) into the L1 cache bypassing the other levels, and for copying > or compacting GC to write it out again bypassing the other levels. I > don't know of a workable solution for sweeping which does modify > structures. Marking involves a WRITE. > Likewise, I can't see how it fixes circular linking ... all FIFOO > seems intended to do is provide a way to find the roots of structures > that share common sub-structure. I didn't see any provision to > prevent circular linking. It seems to me to be a heavy-weight > solution to the problem - in the absence of tracing or copying GC, Tail self linking becomes 'conceptually' impossible/not supported, and circular linking can be found by common tail => i.e. will be one of the heads, and so will share a common tail. So an object traversal of all heads to check not common tail ... a reduction in computation for self referencing structures, and an easy active head count = 0 test for complete free, which will keep you in list elements for quite a while before any complex gc code has to be run. FIFOO does not prevent self references, but makes it easier to computationally detect if necessary. Mark sweep involves marking the whole active list node set. Three total traversals or two if a binary bool marker is used. Allocate copy involves handles to every list node or a referer node list for back poking, and involves full traversal of the active node list and reallocation and copying of them. > ISTM that using an object table to indirectly reference objects with > multiple parents is a better solution ... delete/sweep of an object > stops where it chases a pointer into the object table. Apart from TABLE being associated with heap compaction/fragmentation issues, could you elaborate. To me it seems like any node which has more than one referrer, referers to it through a handle in the table. What of just one referrer and the extra bool? How is in table detected? How are circular references handled or avoided? (by a handle of course, but...) How is self reference handled or avoided? If I understand you it's about kind of a join node inserted transparently agregated in the table with all the other join nodes, and including a referer count and a node class indication. So that forces some kind of count and class per node rather than per structure. So more than 2 machine words per node? Cheers Jacko
From: jacko on 15 Jul 2010 15:47 On Jul 15, 7:35 pm, George Neuner <gneun...(a)comcast.net> wrote: > On Thu, 15 Jul 2010 09:09:52 -0700 (PDT), jacko <jackokr...(a)gmail.com> > wrote: > > > > > > >On Jul 15, 4:48 pm, George Neuner <gneun...(a)comcast.net> wrote: > >> On Thu, 15 Jul 2010 08:17:44 -0700 (PDT), jacko <jackokr...(a)gmail.com> > >> wrote: > > >> >Is > > >> >http://groups.google.com/group/comp.lang.forth/browse_thread/thread/4... > > >> >important for solving the GC problem? Ref FIFOO > > >> There isn't enough detail in that conversation to figure out what > >> problem the structure is trying to solve. What exactly are you > >> asking? > > >> George > > >From my own prospective the mark and sweep cache flushing garbage > >collector problem. Also related to the circular pointer counted > >reference memory leak problem, and the common tail evaluation of > >circular structures solution. > > I don't see how the "FIFOO" described in the link would help cache > pollution in GC (any GC). Since marking and copying are both > read-only (no modify) operations, the best solution is to fetch the > value(s) into the L1 cache bypassing the other levels, and for copying > or compacting GC to write it out again bypassing the other levels. I > don't know of a workable solution for sweeping which does modify > structures. Marking involves a WRITE. > Likewise, I can't see how it fixes circular linking ... all FIFOO > seems intended to do is provide a way to find the roots of structures > that share common sub-structure. I didn't see any provision to > prevent circular linking. It seems to me to be a heavy-weight > solution to the problem - in the absence of tracing or copying GC, Tail self linking becomes 'conceptually' impossible/not supported, and circular linking can be found by common tail => i.e. will be one of the heads, and so will share a common tail. So an object traversal of all heads to check not common tail ... a reduction in computation for self referencing structures, and an easy active head count = 0 test for complete free, which will keep you in list elements for quite a while before any complex gc code has to be run. FIFOO does not prevent self references, but makes it easier to computationally detect if necessary. Mark sweep involves marking the whole active list node set. Three total traversals or two if a binary bool marker is used. Allocate copy involves handles to every list node or a referer node list for back poking, and involves full traversal of the active node list and reallocation and copying of them. > ISTM that using an object table to indirectly reference objects with > multiple parents is a better solution ... delete/sweep of an object > stops where it chases a pointer into the object table. Apart from TABLE being associated with heap compaction/fragmentation issues, could you elaborate. To me it seems like any node which has more than one referrer, referers to it through a handle in the table. What of just one referrer and the extra bool? How is in table detected? How are circular references handled or avoided? (by a handle of course, but...) How is self reference handled or avoided? If I understand you it's about kind of a join node inserted transparently agregated in the table with all the other join nodes, and including a referer count and a node class indication. So that forces some kind of count and class per node rather than per structure. So more than 2 machine words per node? Cheers Jacko
From: jacko on 15 Jul 2010 19:48
http://groups.google.com/group/comp.lang.misc/browse_thread/thread/35967349de8446c1# The strong non circularity argument. |