Ignore:
Timestamp:
Aug 12, 2025, 12:44:35 AM (7 weeks ago)
Author:
Michael Brooks <mlbrooks@…>
Branches:
master
Children:
7f995d70
Parents:
81e1984b
Message:

Revise data in linked-list plots with streamlined harness and data from runs on swift.

No change to text discussing the plots, so some of that discussion is now stale.

Harness changes allow more ifdef feature disabling and eliminate side-array usage, keeping all per-node harness state inside the list nodes.

Completely disable the interleaving experiment, which was not giving discernable data.

File:
1 edited

Legend:

Unmodified
Added
Removed

  • doc/theses/mike_brooks_MMath/benchmarks/list/libcfa-fork-list.hfa

    r81e1984b r6c58850  
    8484// signifying, "need to advance to the first element," and at the end
    8585// of iteration, signifying, "no more elements."  Normal comsumption of
    86 // an iterator runs ?`moveNext as the first step, and uses the return
    87 // of ?`moveNext as a guard, before dereferencing the iterator.  So
     86// an iterator runs advance as the first step, and uses the return
     87// of advance as a guard, before dereferencing the iterator.  So
    8888// normal consumption of an iterator does not dereference an iterator
    8989// in origin position.  The value of a pointer (underlying a refence)
    … …  
    342342    }
    343343
    344     static inline tE & ?`first( dlist(tE, tLinks) & lst ) {
     344    static inline tE & first( dlist(tE, tLinks) & lst ) {
    345345                verify (&lst != 0p);
    346346        dlink(tE) * firstLnk = lst.next;
    … …  
    349349        return downcast$( firstLnkTagged );
    350350    }
    351     static inline tE & ?`last ( dlist(tE, tLinks) & lst ) {
     351    static inline tE & last ( dlist(tE, tLinks) & lst ) {
    352352                verify (&lst != 0p);
    353353        dlink(tE) * lastLnk = lst.prev;
    … …  
    357357    }
    358358
    359     static inline bool ?`isEmpty( dlist(tE, tLinks) & lst ) {
     359    static inline bool isEmpty( dlist(tE, tLinks) & lst ) {
    360360                verify (&lst != 0p);
    361         if ( & lst`first == 0p || & lst`last == 0p ) {
    362             verify( & lst`last == 0p && & lst`last == 0p );
     361        if ( & first(lst) == 0p || & last(lst) == 0p ) {
     362            verify( & last(lst) == 0p && & last(lst) == 0p );
    363363            return true;
    364364        }
    … …  
    366366    }
    367367
    368     static inline bool ?`isListed( tE & e ) {
     368    static inline bool isListed( tE & e ) {
    369369      NOLOOSE(
    370370                verify (&e != 0p);
    … …  
    381381    }
    382382
    383     static inline tE & ?`elems( dlist(tE, tLinks) & lst ) {
     383    static inline tE & iter( dlist(tE, tLinks) & lst ) {
    384384        tE * origin = $get_list_origin_addr( lst );
    385385        return *origin;
    … …  
    391391    //  tag as in bit manipulation on a funny pointer
    392392
    393     static inline bool ?`moveNext( tE && refx ) {
     393    static inline bool advance( tE && refx ) {
    394394        tE && ref_inner = refx;
    395395        tE & oldReferent = * (tE*) ORIGIN_TAG_CLEAR( (size_t) & ref_inner );
    … …  
    407407    }
    408408
    409     static inline bool ?`movePrev( tE && refx ) {
     409    static inline bool recede( tE && refx ) {
    410410        tE && ref_inner = refx;
    411411        tE & oldReferent = * (tE*) ORIGIN_TAG_CLEAR( (size_t) & ref_inner );
    … …  
    423423    }
    424424
    425     static inline bool hasNext( tE & e ) {
    426         return e`moveNext;
    427     }
    428 
    429     static inline bool hasPrev( tE & e ) {
    430         return e`movePrev;
     425    bool isFirst( tE & node ) {
     426        // Probable bug copied from master
     427        // should be `! recede(node)`
     428        // correct: "is first iff cannot recede"
     429        // used backward in test suite too, probably victim of a grep rename
     430        return recede( node );
     431    }
     432
     433    bool isLast( tE & node ) {
     434        // ditto, vice versa
     435        return advance( node );
    431436    }
    432437
    433438    static inline tE & next( tE & e ) {
    434         if( e`moveNext ) return e;
     439        if( advance(e) ) return e;
    435440        return * 0p;
    436441    }
    437442
    438443    static inline tE & prev( tE & e ) {
    439         if( e`movePrev ) return e;
     444        if( recede(e) ) return e;
    440445        return * 0p;
    441446    }
    … …  
    467472
    468473    static inline void insert_last( dlist(tE, tLinks) &lst, tE & e ) {
    469         // insert_before(lst`elems, e);
     474        // insert_before(iter(lst), e);
    470475        dlink(tE) & linkToInsert = e`inner;
    471476                verify(ORIGIN_TAG_QUERY((size_t)linkToInsert.next));
    … …  
    490495    static inline tE & remove_first( dlist(tE, tLinks) &lst ) {
    491496                verify (&lst != 0p);
    492         dlink(tE) & before_links = lst;
    493         verify (! ORIGIN_TAG_QUERY( (size_t) (before_links.next) ) );
    494 
    495         dlink(tE) & list_pos_links = * before_links.next;
    496         dlink(tE) & before_raw = * list_pos_links.prev;
    497 
    498         dlink(tE) & after_raw = * list_pos_links.next;
     497        dlink(tE) & list_links = lst;
     498        verify (! ORIGIN_TAG_QUERY( (size_t) (list_links.next) ) );
     499
     500        dlink(tE) & fst_links = * list_links.next;
     501
     502        dlink(tE) & after_raw = * fst_links.next;
    499503        dlink(tE) & after_links = * (dlink(tE) *) ORIGIN_TAG_CLEAR( (size_t) & after_raw );
    500         size_t after_links_prev_tag = ORIGIN_TAG_QUERY( (size_t) (after_links.prev) );
     504        verify( ! ORIGIN_TAG_QUERY( (size_t) (after_links.prev) ) );
    501505
    502506        size_t before_links_next_rslt = ((size_t) & after_raw);
    503         size_t after_links_prev_rslt = ORIGIN_TAG_ASGN( ((size_t) & before_raw), after_links_prev_tag );
    504         before_links.next = (dlink(tE) *) before_links_next_rslt;
     507        size_t after_links_prev_rslt = ORIGIN_TAG_ENABL( (size_t) & list_links );
     508        list_links.next = (dlink(tE) *) before_links_next_rslt;
    505509        after_links.prev = (dlink(tE) *) after_links_prev_rslt;
    506510
    507511        asm( "" : : : "memory" );
    508         size_t list_pos_links_num = (size_t) &list_pos_links;
     512        size_t list_pos_links_num = (size_t) &fst_links;
    509513        size_t list_pos_links_tagged_num = ORIGIN_TAG_ENABL( list_pos_links_num );
    510                 list_pos_links.next = list_pos_links.prev = (dlink(tE)*) list_pos_links_tagged_num;
    511         asm( "" : : : "memory" );
    512 
    513         tytagref( tLinks, dlink(tE) ) lpLnkTagged = {list_pos_links};
     514                fst_links.next = fst_links.prev = (dlink(tE)*) list_pos_links_tagged_num;
     515        asm( "" : : : "memory" );
     516
     517        tytagref( tLinks, dlink(tE) ) lpLnkTagged = {fst_links};
    514518        return downcast$( lpLnkTagged );
    515519    }
    … …  
    517521    static inline tE & remove_last( dlist(tE, tLinks) &lst ) {
    518522                verify (&lst != 0p);
    519         dlink(tE) & after_links = lst;
    520         verify (! ORIGIN_TAG_QUERY( (size_t) (after_links.prev) ) );
    521 
    522         dlink(tE) & list_pos_links = * after_links.prev;
    523         dlink(tE) & after_raw = * list_pos_links.next;
    524 
    525         dlink(tE) & before_raw = * list_pos_links.prev;
     523        dlink(tE) & list_links = lst;
     524        verify (! ORIGIN_TAG_QUERY( (size_t) (list_links.prev) ) );
     525
     526        dlink(tE) & last_links = * list_links.prev;
     527
     528        dlink(tE) & before_raw = * last_links.prev;
    526529        dlink(tE) & before_links = * (dlink(tE) *) ORIGIN_TAG_CLEAR( (size_t) & before_raw );
    527         size_t before_links_next_tag = ORIGIN_TAG_QUERY( (size_t) (before_links.next) );
     530        verify( ! ORIGIN_TAG_QUERY( (size_t) (before_links.next) ) );
    528531
    529532        size_t after_links_prev_rslt = ((size_t) & before_raw);
    530         size_t before_links_next_rslt = ORIGIN_TAG_ASGN( ((size_t) & after_raw), before_links_next_tag );
    531         after_links.prev = (dlink(tE) *) after_links_prev_rslt;
     533        size_t before_links_next_rslt = ORIGIN_TAG_ENABL( (size_t) & list_links );
     534        list_links.prev = (dlink(tE) *) after_links_prev_rslt;
    532535        before_links.next = (dlink(tE) *) before_links_next_rslt;
    533536
    534537        asm( "" : : : "memory" );
    535         size_t list_pos_links_num = (size_t) &list_pos_links;
     538        size_t list_pos_links_num = (size_t) &last_links;
    536539        size_t list_pos_links_tagged_num = ORIGIN_TAG_ENABL( list_pos_links_num );
    537                 list_pos_links.prev = list_pos_links.next = (dlink(tE)*) list_pos_links_tagged_num;
    538         asm( "" : : : "memory" );
    539 
    540         tytagref( tLinks, dlink(tE) ) lpLnkTagged = {list_pos_links};
     540                last_links.prev = last_links.next = (dlink(tE)*) list_pos_links_tagged_num;
     541        asm( "" : : : "memory" );
     542
     543        tytagref( tLinks, dlink(tE) ) lpLnkTagged = {last_links};
    541544        return downcast$( lpLnkTagged );
    542545    }
    543546
    544     static inline tE & try_pop_front( dlist(tE, tLinks) &lst ) {
    545         tE & first_inlist = lst`first;
     547    static inline tE & try_pop_first( dlist(tE, tLinks) &lst ) {
     548        tE & first_inlist = first(lst);
    546549        tE & first_item = first_inlist;
    547550        if (&first_item) remove(first_inlist);  // TODO: should it use pop_front?
    … …  
    549552    }
    550553
    551     static inline tE & try_pop_back( dlist(tE, tLinks) &lst ) {
    552         tE & last_inlist = lst`last;
     554    static inline tE & try_pop_last( dlist(tE, tLinks) &lst ) {
     555        tE & last_inlist = last(lst);
    553556        tE & last_item = last_inlist;
    554557        if (&last_item) remove(last_inlist);  // TODO: should it use pop_back?
    … …  
    561564        tE & lagElem = *0p;
    562565
    563         while ( tE & it = this`elems; it`moveNext ) {
    564             if (& lagElem == 0p &&  &it != & this`first ) return false;
     566        while ( tE & it = iter(this); advance(it) ) {
     567            if (& lagElem == 0p &&  &it != & first(this) ) return false;
    565568            & lagElem = & it;
    566569        }
    567570
    568         if (& lagElem != & this`last) return false;
    569 
    570         // TODO: verify that it is back at this`elems;
     571        if (& lagElem != & last(this)) return false;
     572
     573        // TODO: verify that it is back at iter(this);
    571574        return true;
    572575        }
    … …  
    574577        tE & lagElem = *0p;
    575578
    576         while ( tE & it = this`elems; it`movePrev ) {
    577             if (& lagElem == 0p &&  &it != & this`last ) return false;
     579        while ( tE & it = iter(this); recede(it) ) {
     580            if (& lagElem == 0p &&  &it != & last(this) ) return false;
    578581            & lagElem = & it;
    579582        }
    580583
    581         if (& lagElem != & this`first) return false;
    582 
    583         // TODO: verify that it is back at this`elems;
     584        if (& lagElem != & first(this)) return false;
     585
     586        // TODO: verify that it is back at iter(this);
    584587        return true;
    585588        }
    586589        static inline bool validate( dlist(tE, tLinks) & this ) {
    587         bool reportsHavingFirst = ((& this`first) == 0p);
    588         bool reportsHavingLast = ((& this`last) == 0p);
     590        bool reportsHavingFirst = ((& first(this)) == 0p);
     591        bool reportsHavingLast = ((& last(this)) == 0p);
    589592        if ( reportsHavingFirst != reportsHavingLast ) return false;
    590593
Note: See TracChangeset for help on using the changeset viewer.