Changeset 08ed947 for libcfa


Ignore:
Timestamp:
Feb 23, 2022, 6:13:02 PM (2 years ago)
Author:
Michael Brooks <mlbrooks@…>
Branches:
ADT, ast-experimental, enum, master, pthread-emulation, qualifiedEnum
Children:
afe9e45, c5af4f9
Parents:
cc7bbe6
Message:

Roll up of string changes for performance testing/improvement, and a couple API features supporting them.

String API changes:
Defining a tuning knob to control the heap growth policy (relapaces former 10% hardcode, downgraded to a default)
Implementing findFrom (allowing find-non-first); leaving find as find-first.

String implementation perf improvements:
Calling C-malloc directly instead of via CFA-alloc.
Replacings loops that copy with memmove calls.
Replacings loops that search for a value with memchr calls.

String perf testing realized:
Makefile supporting several prog-*.cfa, chosen by OPERATION value (implies prog.cfa changes to support the adjusted protocol)
Adjusting the starter/accumulater declarations in PEQ and PTA to behave consistently in cfa v cpp.
Adding tests: allocation, find, normalize, pass-by-val, pass-by-x.
Adding helper shell scripts for: generating flame graphs, collecting/crunching allocation stats using Mubeen's malloc wrappers

Location:
libcfa/src/containers
Files:
4 edited

Legend:

Unmodified
Added
Removed

  • libcfa/src/containers/string.cfa

    rcc7bbe6 r08ed947  
    237237}
    238238
     239int findFrom(const string &s, size_t fromPos, char search) {
     240    return findFrom( *s.inner, fromPos, search );
     241}
     242
     243int findFrom(const string &s, size_t fromPos, const string &search) {
     244    return findFrom( *s.inner, fromPos, *search.inner );
     245}
     246
     247int findFrom(const string &s, size_t fromPos, const char* search) {
     248    return findFrom( *s.inner, fromPos, search );
     249}
     250
     251int findFrom(const string &s, size_t fromPos, const char* search, size_t searchsize) {
     252    return findFrom( *s.inner, fromPos, search, searchsize );
     253}
     254
    239255bool includes(const string &s, const string &search) {
    240256    return includes( *s.inner, *search.inner );

  • libcfa/src/containers/string.hfa

    rcc7bbe6 r08ed947  
    9393int find(const string &s, const char* search, size_t searchsize);
    9494
     95int findFrom(const string &s, size_t fromPos, char search);
     96int findFrom(const string &s, size_t fromPos, const string &search);
     97int findFrom(const string &s, size_t fromPos, const char* search);
     98int findFrom(const string &s, size_t fromPos, const char* search, size_t searchsize);
     99
    95100bool includes(const string &s, const string &search);
    96101bool includes(const string &s, const char* search);

  • libcfa/src/containers/string_res.cfa

    rcc7bbe6 r08ed947  
    1616#include "string_res.hfa"
    1717#include "string_sharectx.hfa"
    18 
    19 #include <stdlib.hfa>  // e.g. malloc
     18#include "stdlib.hfa"
     19
     20// Workaround for observed performance penalty from calling CFA's alloc.
     21// Workaround is:  EndVbyte = TEMP_ALLOC(char, CurrSize)
     22// Should be:      EndVbyte = alloc(CurrSize)
     23#define TEMP_ALLOC(T, n) (( T* ) malloc( n * sizeof( T ) ))
     24
    2025#include <assert.h>
    2126
    … …  
    6772    NoOfCompactions = NoOfExtensions = NoOfReductions = 0;
    6873    InitSize = CurrSize = Size;
    69     StartVbyte = EndVbyte = alloc(CurrSize);
     74    StartVbyte = EndVbyte = TEMP_ALLOC(char, CurrSize);
    7075    ExtVbyte = (void *)( StartVbyte + CurrSize );
    7176    Header.flink = Header.blink = &Header;
    … …  
    246251    Handle.s = VbyteAlloc(*Handle.ulink, rhslnth);
    247252    Handle.lnth = rhslnth;
    248     for ( int i = 0; i < rhslnth; i += 1 ) {            // copy characters
    249         Handle.s[i] = rhs[i];
    250     } // for
     253    memmove( Handle.s, rhs, rhslnth );
    251254    s.shareEditSet_prev = &s;
    252255    s.shareEditSet_next = &s;
    … …  
    264267    Handle.lnth = rhslnth;
    265268    (s.shareEditSet_owns_ulink){ false };
    266     for ( int i = 0; i < rhslnth; i += 1 ) {            // copy characters
    267         Handle.s[i] = rhs[i];
    268     } // for
     269    memmove( Handle.s, rhs, rhslnth );
    269270    s.shareEditSet_prev = &s;
    270271    s.shareEditSet_next = &s;
    … …  
    595596
    596597int find(const string_res &s, char search) {
    597     for (i; size(s)) {
    598         if (s[i] == search) return i;
    599     }
    600     return size(s);
    601 }
     598    return findFrom(s, 0, search);
     599}
     600
     601int findFrom(const string_res &s, size_t fromPos, char search) {
     602    // FIXME: This paricular overload (find of single char) is optimized to use memchr.
     603    // The general overload (find of string, memchr applying to its first character) and `contains` should be adjusted to match.
     604    char * searchFrom = s.Handle.s + fromPos;
     605    size_t searchLnth = s.Handle.lnth - fromPos;
     606    int searchVal = search;
     607    char * foundAt = (char *) memchr(searchFrom, searchVal, searchLnth);
     608    if (foundAt == 0p) return s.Handle.lnth;
     609    else return foundAt - s.Handle.s;
     610}
     611
     612int find(const string_res &s, const string_res &search) {
     613    return findFrom(s, 0, search);
     614}
     615
     616int findFrom(const string_res &s, size_t fromPos, const string_res &search) {
     617    return findFrom(s, fromPos, search.Handle.s, search.Handle.lnth);
     618}
     619
     620int find(const string_res &s, const char* search) {
     621    return findFrom(s, 0, search);
     622}
     623int findFrom(const string_res &s, size_t fromPos, const char* search) {
     624    return findFrom(s, fromPos, search, strlen(search));
     625}
     626
     627int find(const string_res &s, const char* search, size_t searchsize) {
     628    return findFrom(s, 0, search, searchsize);
     629}
     630
     631int findFrom(const string_res &s, size_t fromPos, const char* search, size_t searchsize) {
    602632
    603633    /* Remaining implementations essentially ported from Sunjay's work */
    604634
    605 int find(const string_res &s, const string_res &search) {
    606     return find(s, search.Handle.s, search.Handle.lnth);
    607 }
    608 
    609 int find(const string_res &s, const char* search) {
    610     return find(s, search, strlen(search));
    611 }
    612 
    613 int find(const string_res &s, const char* search, size_t searchsize) {
     635
    614636    // FIXME: This is a naive algorithm. We probably want to switch to someting
    615637    // like Boyer-Moore in the future.
    … …  
    621643    }
    622644
    623     for (size_t i = 0; i < s.Handle.lnth; i++) {
     645    for (size_t i = fromPos; i < s.Handle.lnth; i++) {
    624646        size_t remaining = s.Handle.lnth - i;
    625647        // Never going to find the search string if the remaining string is
    … …  
    740762    serr | "enter:AddThisAfter, this:" | &this | " n:" | &n;
    741763#endif // VbyteDebug
     764    // Performance note: we are on the critical path here. MB has ensured that the verifies don't contribute to runtime (are compiled away, like they're supposed to be).
    742765    verify( n.ulink != 0p );
    743766    verify( this.ulink == n.ulink );
    … …  
    823846    NoOfExtensions += 1;
    824847    CurrSize *= 2;
    825     StartVbyte = EndVbyte = alloc(CurrSize);
     848    StartVbyte = EndVbyte = TEMP_ALLOC(char, CurrSize);
    826849    ExtVbyte = StartVbyte + CurrSize;
    827850
    … …  
    959982
    960983
     984static double heap_expansion_freespace_threshold = 0.1;  // default inherited from prior work: expand heap when less than 10% "free" (i.e. garbage)
     985                                                         // probably an unreasonable default, but need to assess early-round tests on changing it
     986
     987void TUNING_set_string_heap_liveness_threshold( double val ) {
     988    heap_expansion_freespace_threshold = 1.0 - val;
     989}
     990
     991
    961992// Garbage determines the amount of free space left in the heap and then reduces, leave the same, or extends the size of
    962993// the heap.  The heap is then compacted in the existing heap or into the newly allocated heap.
    … …  
    9861017    AmountFree = ( uintptr_t )ExtVbyte - ( uintptr_t )StartVbyte - AmountUsed;
    9871018   
    988     if ( ( double ) AmountFree < ( CurrSize * 0.1 ) || AmountFree < minreq ) {  // free space less than 10% or not enough to serve cur request
     1019    if ( ( double ) AmountFree < ( CurrSize * heap_expansion_freespace_threshold ) || AmountFree < minreq ) {   // free space less than threshold or not enough to serve cur request
    9891020
    9901021                extend( this, max( CurrSize, minreq ) );                                // extend the heap
    … …  
    10331064   
    10341065    CurrSize += size > InitSize ? size : InitSize;      // minimum extension, initial size
    1035     StartVbyte = EndVbyte = alloc(CurrSize);
     1066    StartVbyte = EndVbyte = TEMP_ALLOC(char, CurrSize);
    10361067    ExtVbyte = (void *)( StartVbyte + CurrSize );
    10371068    compaction(this);                                   // copy from old heap to new & adjust pointers to new heap

  • libcfa/src/containers/string_res.hfa

    rcc7bbe6 r08ed947  
    3939const char * DEBUG_string_heap_start( VbyteHeap * heap );
    4040
     41void TUNING_set_string_heap_liveness_threshold( double val );
    4142
    4243//######################### String #########################
    … …  
    128129int find(const string_res &s, const char* search, size_t searchsize);
    129130
     131int findFrom(const string_res &s, size_t fromPos, char search);
     132int findFrom(const string_res &s, size_t fromPos, const string_res &search);
     133int findFrom(const string_res &s, size_t fromPos, const char* search);
     134int findFrom(const string_res &s, size_t fromPos, const char* search, size_t searchsize);
     135
    130136bool includes(const string_res &s, const string_res &search);
    131137bool includes(const string_res &s, const char* search);
Note: See TracChangeset for help on using the changeset viewer.