Changeset 8291293


Ignore:
Timestamp:
Jul 1, 2020, 12:13:41 PM (15 months ago)
Author:
Thierry Delisle <tdelisle@…>
Branches:
arm-eh, jacob/cs343-translation, master, new-ast, new-ast-unique-expr
Children:
c33ed65
Parents:
398e8e9 (diff), 9f7fff4 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.
Message:

Merge branch 'master' of plg.uwaterloo.ca:software/cfa/cfa-cc

File:
1 edited

Legend:

Unmodified
Added
Removed
  • examples/hashtable2.cfa

    r398e8e9 r8291293  
    3232DATA_EXCEPTION(ht_fill_limit_crossed)(
    3333        void * theHashtable;
     34    bool want_throwResume_ht_auto_resize_pending;
     35    size_t size_for_ht_auto_resize_pending;
    3436);
    3537
     
    3739        VTABLE_INIT(this, ht_fill_limit_crossed);
    3840        this.theHashtable = theHashtable;
     41    this.want_throwResume_ht_auto_resize_pending = false;
     42    this.size_for_ht_auto_resize_pending = 0;
    3943}
    4044
     
    4549VTABLE_INSTANCE(ht_fill_limit_crossed)(ht_fill_limit_crossed_msg);
    4650
     51
     52DATA_EXCEPTION(ht_auto_resize_pending)(
     53        void * theHashtable;
     54    size_t new_size;
     55);
     56
     57void ?{}(ht_auto_resize_pending & this, void * theHashtable, size_t new_size) {
     58        VTABLE_INIT(this, ht_auto_resize_pending);
     59        this.theHashtable = theHashtable;
     60    this.new_size = new_size;
     61}
     62
     63const char * ht_auto_resize_pending_msg(ht_auto_resize_pending * this) {
     64        return "ht_auto_resize_pending";
     65}
     66
     67VTABLE_INSTANCE(ht_auto_resize_pending)(ht_auto_resize_pending_msg);
    4768
    4869
     
    7596        size_t item_count;
    7697        float ff_next_warn_up;
     98        float ff_warn_step_factor;
    7799
    78100        void (*defaultResumptionHandler) (ht_fill_limit_crossed &);
     
    84106forall( otype Tt_unused | pretendsToMatter(Tt_unused) | { void defaultResumptionHandler(ht_fill_limit_crossed &); } ) {
    85107
    86     void ?{}( hashtable_rbs(Tt_unused) & this, size_t n_buckets, dlist(request_in_ht_by_src, request) *buckets ) {
     108    void ?{}( hashtable_rbs(Tt_unused) & this, size_t n_buckets, dlist(request_in_ht_by_src, request) *buckets,
     109        float ff_next_warn_up, float ff_warn_step_factor ) {
     110
     111        printf( "base hashtable ctor with %ld buckets at %p\n", n_buckets, buckets);
    87112
    88113        this.n_buckets = n_buckets;
     
    90115
    91116        this.item_count = 0;
    92         this.ff_next_warn_up = 0.5;
     117        this.ff_next_warn_up = ff_next_warn_up;
     118        this.ff_warn_step_factor = ff_warn_step_factor;
    93119
    94120        this.defaultResumptionHandler = defaultResumptionHandler;
     
    98124        }
    99125    }
    100 }
    101 
     126
     127    void ?{}( hashtable_rbs(Tt_unused) & this, size_t n_buckets, dlist(request_in_ht_by_src, request) *buckets ) {
     128        printf( "base hashtable ctor with default warning steps\n" );
     129        ( this ) { n_buckets, buckets, 0.5, 2 };
     130    }
     131
     132}
     133
     134// this fwd declaration is artifact of workaround trac#192
     135void defaultResumptionHandler( ht_auto_resize_pending & ex );
    102136
    103137forall( otype Tt_unused | pretendsToMatter(Tt_unused) ) {
     
    126160    void check_ff_warning( hashtable_rbs(Tt_unused) & this ) with (this) {
    127161        if (fill_frac(this) > ff_next_warn_up) {
    128             throwResume (ht_fill_limit_crossed){ &this };
     162            ht_fill_limit_crossed ex1 = { &this };
     163            throwResume ex1;
     164            // workaround trac#192: want the second throwResume to be in __dynamic_defaultResumptionHandler
     165            // ... want base hashtable decoupled from resize
     166            if ( ex1.want_throwResume_ht_auto_resize_pending ) {
     167                throwResume( (ht_auto_resize_pending) { & this, ex1.size_for_ht_auto_resize_pending } );
     168            }
    129169        }
    130170    }
     
    170210
    171211void defaultResumptionHandler(ht_fill_limit_crossed & ex) {
    172     printf("default resumption ht_fill_limit_crossed\n");
    173212    hashtable_rbs(t_unused) & ht = *(hashtable_rbs(t_unused) *)ex.theHashtable;
    174     ht.ff_next_warn_up *= 2;
     213    printf("base default resumption handler ht_fill_limit_crossed with ht filled at %f\n", fill_frac(ht));
     214    ht.ff_next_warn_up *= ht.ff_warn_step_factor;
    175215}
    176216
     
    192232    struct hashtable_rbs_dynamic {
    193233        inline hashtable_rbs(Tt_unused);
     234
     235        struct resize_policy {
     236            // When fill factor exceeds grow limit, grow big enough for
     237            // resulting fill factor to be lower than grow_target.  Vice versa.
     238            // Using different grow and shrink limits prevents noisy current
     239            // size from triggering grow-shrink oscillation.  OK to use same
     240            // grow and shrink targets.
     241            float grow_limit, shrink_limit, grow_target, shrink_target;
     242
     243            // warn with exception but do nothing, this many -1 times, then actually resize
     244            unsigned short int warns_per_grow, warns_per_shrink;
     245
     246            // Don't shrink below.
     247            size_t nbuckets_floor;
     248        } policy;
     249
    194250        dlist(request_in_ht_by_src, request) * (*alloc)( size_t );
    195251        void (*free)( void * );
     
    209265forall( otype Tt_unused | heaped( dlist(request_in_ht_by_src, request) ) ) {
    210266
    211     void ?{}( hashtable_rbs_dynamic(Tt_unused) & this, size_t n_buckets )  {
     267    void ?{}( hashtable_rbs_dynamic(Tt_unused).resize_policy & this, size_t nbuckets_floor ) {
     268        printf("default dynamic policy ctor\n");
     269
     270        (this.grow_limit)      {2.0};
     271        (this.shrink_limit)    {0.5};
     272        (this.grow_target)     {1.0};
     273        (this.shrink_target)   {1.0};
     274        (this.warns_per_grow)  {4};
     275        (this.warns_per_shrink){4};
     276        (this.nbuckets_floor)  {nbuckets_floor};
     277    }
     278
     279    void ?{}( hashtable_rbs_dynamic(Tt_unused) & this, size_t n_buckets, hashtable_rbs_dynamic(Tt_unused).resize_policy rp )  {
     280        printf("ctor hashtable_rbs_dynamic{ size_t, resize_policy }\n");
     281
     282        float first_first_warn_up = rp.grow_target;
     283        float ff_warn_step_factor = (rp.grow_limit / rp.grow_target) \ ( 1. / rp.warns_per_grow );
     284
    212285        void (*defaultResumptionHandler) (ht_fill_limit_crossed &) = __dynamic_defaultResumptionHandler;
    213286        dlist(request_in_ht_by_src, request) *buckets = alloc(n_buckets);
    214         ((hashtable_rbs(Tt_unused) &)this){ n_buckets, buckets };
     287        ( ( hashtable_rbs( Tt_unused ) & ) this ){ n_buckets, buckets, first_first_warn_up, ff_warn_step_factor };
     288        ( this.policy ){ rp };
    215289        this.alloc = alloc;
    216290        this.free = free;
     291    }
     292    void ?{}( hashtable_rbs_dynamic(Tt_unused) & this, hashtable_rbs_dynamic(Tt_unused).resize_policy rp )  {
     293        printf("ctor hashtable_rbs_dynamic{ resize_policy }\n");
     294        ( this ) { rp.nbuckets_floor, rp };
     295    }
     296    void ?{}( hashtable_rbs_dynamic(Tt_unused) & this, size_t n_buckets )  {
     297        printf("ctor hashtable_rbs_dynamic{ size_t }\n");
     298        ( this ) { n_buckets, (hashtable_rbs_dynamic(Tt_unused).resize_policy){ n_buckets } };
    217299    }
    218300    void ^?{}( hashtable_rbs_dynamic(Tt_unused) & this ) {
     
    230312        // make empty hash table of new size
    231313        dlist(request_in_ht_by_src, request) *oldBuckets = buckets;
     314        float oldFfWarnStepFactor = ff_warn_step_factor;
     315        float newFfNextWarnUp = ((float)item_count) / ((float) new_n_buckets);
    232316        ^?{}( (hashtable_rbs(Tt_unused) &)this );
    233317        free( oldBuckets );
    234         ?{}( (hashtable_rbs(Tt_unused) &)this, new_n_buckets, alloc(new_n_buckets) );
     318        ?{}( (hashtable_rbs(Tt_unused) &)this, new_n_buckets, alloc(new_n_buckets), newFfNextWarnUp, oldFfWarnStepFactor );
    235319
    236320        // fill new table with old items
     
    247331}
    248332
     333void defaultResumptionHandler( ht_auto_resize_pending & ex ) {
     334    hashtable_rbs_dynamic(t_unused) & ht = *(hashtable_rbs_dynamic(t_unused) *)ex.theHashtable;
     335    printf("auto-resize unhandled: proceeding with resize\n");
     336    rehashToLarger_STEP( ht, ex.new_size );
     337}
     338
    249339void __dynamic_defaultResumptionHandler(ht_fill_limit_crossed & ex) {
    250340    hashtable_rbs_dynamic(t_unused) & ht = *(hashtable_rbs_dynamic(t_unused) *)ex.theHashtable;
    251     printf("dynamic limit crossed with fill_frac = %f and buckets at %p\n", fill_frac(ht), ht.buckets);
    252     rehashToLarger_STEP( ht, 2 * ht.n_buckets );
     341    printf("dynamic warning received with fill_frac = %f and buckets at %p\n", fill_frac(ht), ht.buckets);
     342    if ( fill_frac( ht ) >= ht.policy.grow_limit ) {
     343        float grow_amount =  ht.policy.grow_limit / ht.policy.grow_target;
     344        ex.want_throwResume_ht_auto_resize_pending = true;
     345        ex.size_for_ht_auto_resize_pending = ( size_t )( grow_amount * ht.n_buckets );
     346    } else {
     347        // base handler, not specialized for dynamic
     348        defaultResumptionHandler( ex );
     349    }
    253350}
    254351
     
    260357#include <stdlib.hfa>
    261358
    262 int main() {
    263 
    264 
    265     HASHTABLE_RBS_STATIC(67, h_src)
    266 
    267     request & wasnt_found = get(h_src, 17);
     359void basicFillingTestHelper( hashtable_rbs(t_unused) & ht, size_t n_elems ) {
     360
     361    request & wasnt_found = get(ht, 17);
    268362    assert( &wasnt_found == 0p );
    269363
     
    272366    r.tgt_id = 998;
    273367
    274     put(h_src, r);
    275 
    276     request & found = get(h_src, 117);
     368    put(ht, r);
     369
     370    request & found = get(ht, 117);
    277371    assert( &found == &r );
    278372
    279     & wasnt_found = & get(h_src, 998);
     373    & wasnt_found = & get(ht, 998);
    280374    assert( &wasnt_found == 0p );
    281375
    282     printf( "%f\n", fill_frac(h_src) );
    283 
    284 
    285     request rs[500];
    286     try {
    287         for (i; 500) {
    288             rs[i].src_id = 8000 * i;
    289             put(h_src, rs[i]);
    290         }
    291     } catchResume(ht_fill_limit_crossed*) {
    292         printf("fill limit tripped with h_src filled at %f\n", fill_frac(h_src));
    293         throwResume;
    294     }
    295 
    296     assert(  & get(h_src, 117      ) );
    297     assert(  & get(h_src, 8000*25  ) );
    298     assert(! & get(h_src, 8000*25+1) );
    299 
    300 
     376    request rs[n_elems];
     377    for (i; n_elems) {
     378        rs[i].src_id = 8000 * i;
     379        put(ht, rs[i]);
     380    }
     381
     382    assert(  & get(ht, 117      ) );
     383    assert(  & get(ht, 8000*25  ) );
     384    assert(! & get(ht, 8000*25+1) );
     385}
     386
     387void basicFillingTest_static() {
     388
     389    printf("---start basic fill test static ----\n");
     390
     391    HASHTABLE_RBS_STATIC(67, ht)
     392
     393    basicFillingTestHelper(ht, 500);
     394}
     395
     396void basicFillingTest_dynamic() {
    301397
    302398    dlist(request_in_ht_by_src, request) * (*old_alloc)( size_t ) = alloc;
     
    313409    }
    314410
    315     hashtable_rbs_dynamic(t_unused) ht2 = { 113 };
    316     request rs2[500];
     411    printf("---start basic fill test dynamic ----\n");
     412
     413    hashtable_rbs_dynamic(t_unused) ht = { 113 };
     414
     415    basicFillingTestHelper(ht, 500);
     416}
     417
     418// Demonstrates user-provided instrumentation monitoring a fixed-size hash table
     419void logTest() {
     420
     421    printf("---start log test ----\n");
     422
     423    HASHTABLE_RBS_STATIC(67, ht)
     424
    317425    try {
    318         for (i; 500) {
    319             if (i % 10 == 0) {printf("%d(%f),", i, fill_frac(ht2));}
    320             rs2[i].src_id = 8000 * i;
    321             put(ht2, rs2[i]);
    322         }
    323     } catchResume(ht_fill_limit_crossed*) {
    324         printf("fill limit tripped with ht2 filled at %f\n", fill_frac(ht2));
     426        basicFillingTestHelper(ht, 500);
     427    } catchResume( ht_fill_limit_crossed * ) {
     428        printf("log test instrumentation runs\n");
    325429        throwResume;
    326430    }
    327 
    328 
    329 }
     431}
     432
     433// Demonstrates "snoozing" a growing hash table's auto-resize event,
     434// in that that next call to put will get the resize exception instead.
     435void snoozeTest() {
     436
     437    printf("---start snooze test ----\n");
     438
     439    hashtable_rbs_dynamic(t_unused) ht = { 113 };
     440
     441    bool lastResizeSnoozed = false;
     442
     443    try {
     444        basicFillingTestHelper(ht, 500);
     445    } catchResume( ht_auto_resize_pending * ) {
     446
     447        if ( lastResizeSnoozed == false ) {
     448            lastResizeSnoozed = true;
     449            printf("snooze test intervention decides to snooze this time\n");
     450        } else {
     451            lastResizeSnoozed = false;
     452            printf("snooze test intervention decides to allow the resize\n");
     453            throwResume;
     454        }
     455
     456    }
     457}
     458
     459int main() {
     460
     461    basicFillingTest_static();
     462    basicFillingTest_dynamic();
     463
     464    logTest();
     465    snoozeTest();
     466}
Note: See TracChangeset for help on using the changeset viewer.