Ignore:
Timestamp:
Feb 1, 2015, 9:48:36 PM (10 years ago)
Author:
bird
Message:

Optimizations, tuning and bug fixes for the 'compiled' string expansion code.

File:
1 edited

Legend:

Unmodified
Added
Removed

  • trunk/src/kmk/kmk_cc_exec.c

    r2770 r2771  
    4242#include <stdarg.h>
    4343#include <assert.h>
     44
     45/*******************************************************************************
     46*   Defined Constants And Macros                                               *
     47*******************************************************************************/
     48/** @def KMK_CC_WITH_STATS
     49 * Enables the collection of extra statistics. */
     50#ifndef KMK_CC_WITH_STATS
     51# ifdef CONFIG_WITH_MAKE_STATS
     52#  define KMK_CC_WITH_STATS
     53# endif
     54#endif
     55
     56/** @def KMK_CC_STRICT
     57 * Indicates whether assertions and other checks are enabled. */
     58#ifndef KMK_CC_STRICT
     59# ifndef NDEBUG
     60#  define KMK_CC_STRICT
     61# endif
     62#endif
     63
     64#ifdef KMK_CC_STRICT
     65# ifdef _MSC_VER
     66#  define KMK_CC_ASSERT(a_TrueExpr)         do { if (!(a_TrueExpr)) __debugbreak(); } while (0)
     67# else
     68#  define KMK_CC_ASSERT(a_TrueExpr)         assert(a_TrueExpr)
     69# endif
     70#else
     71# define KMK_CC_ASSERT(a_TrueExpr)          do {} while (0)
     72#endif
     73#define KMK_CC_ASSERT_ALIGNED(a_uValue, a_uAlignment) \
     74    KMK_CC_ASSERT( ((a_uValue) & ((a_uAlignment) - 1)) == 0 )
    4475
    4576
    … …  
    264295/** Calculates the size of an KMKCCEXPPLAINFUNC with a_cArgs. */
    265296#define KMKCCEXPDYNFUNC_SIZE(a_cArgs)  (  sizeof(KMKCCEXPFUNCCORE) \
    266                                           + (a_cArgs) * sizeof(((PKMKCCEXPDYNFUNC)(uintptr_t)42)->aArgs[0]) )
     297                                        + (a_cArgs) * sizeof(((PKMKCCEXPDYNFUNC)(uintptr_t)42)->aArgs[0]) )
    267298
    268299/**
    … …  
    289320    /** Statistics. */
    290321    KMKCCEXPSTATS           Stats;
     322#ifdef KMK_CC_STRICT
     323    /** The hash of the input string.  Used to check that we get all the change
     324     * notifications we require. */
     325    uint32_t                uInputHash;
     326#endif
    291327} KMKCCEXPPROG;
    292328/** Pointer to a string expansion program. */
    … …  
    295331
    296332/*******************************************************************************
    297 *   Defined Constants And Macros                                               *
    298 *******************************************************************************/
    299 #ifndef NDEBUG
    300 # ifdef _MSC_VER
    301 #  define KMK_CC_ASSERT(a_TrueExpr)         do { if (!(a_TrueExpr)) __debugbreak(); } while (0)
    302 # else
    303 #  define KMK_CC_ASSERT(a_TrueExpr)         assert(a_TrueExpr)
    304 # endif
    305 #else
    306 # define KMK_CC_ASSERT(a_TrueExpr)          do {} while (0)
    307 #endif
    308 #define KMK_CC_ASSERT_ALIGNED(a_uValue, a_uAlignment) \
    309     KMK_CC_ASSERT( ((a_uValue) & ((a_uAlignment) - 1)) == 0 )
    310 
    311 
    312 /*******************************************************************************
    313333*   Global Variables                                                           *
    314334*******************************************************************************/
     335static uint32_t g_cVarForExpandCompilations = 0;
     336static uint32_t g_cVarForExpandExecs = 0;
     337#ifdef KMK_CC_WITH_STATS
     338static uint32_t g_cBlockAllocated = 0;
     339static uint32_t g_cbAllocated = 0;
     340static uint32_t g_cBlocksAllocatedExpProgs = 0;
     341static uint32_t g_cbAllocatedExpProgs = 0;
     342static uint32_t g_cSingleBlockExpProgs = 0;
     343static uint32_t g_cTwoBlockExpProgs = 0;
     344static uint32_t g_cMultiBlockExpProgs = 0;
     345static uint32_t g_cbUnusedMemExpProgs = 0;
     346#endif
    315347
    316348
    … …  
    331363
    332364/**
     365 * Prints stats (for kmk -p).
     366 */
     367void kmk_cc_print_stats(void)
     368{
     369    puts(_("\n# The kmk 'compiler' and kmk 'program executor':\n"));
     370
     371    printf(_("# Variables compiled for string expansion: %6u\n"), g_cVarForExpandCompilations);
     372    printf(_("# Variables string expansion runs:         %6u\n"), g_cVarForExpandExecs);
     373    printf(_("# String expansion runs per compile:       %6u\n"), g_cVarForExpandExecs / g_cVarForExpandExecs);
     374#ifdef KMK_CC_WITH_STATS
     375    printf(_("#          Single alloc block exp progs:   %6u (%u%%)\n"
     376             "#             Two alloc block exp progs:   %6u (%u%%)\n"
     377             "#   Three or more alloc block exp progs:   %6u (%u%%)\n"
     378             ),
     379           g_cSingleBlockExpProgs, (uint32_t)((uint64_t)g_cSingleBlockExpProgs * 100 / g_cVarForExpandCompilations),
     380           g_cTwoBlockExpProgs,    (uint32_t)((uint64_t)g_cTwoBlockExpProgs    * 100 / g_cVarForExpandCompilations),
     381           g_cMultiBlockExpProgs,  (uint32_t)((uint64_t)g_cMultiBlockExpProgs  * 100 / g_cVarForExpandCompilations));
     382    printf(_("#  Total amount of memory for exp progs: %8u bytes\n"
     383             "#                                    in:   %6u blocks\n"
     384             "#                        avg block size:   %6u bytes\n"
     385             "#                         unused memory: %8u bytes (%u%%)\n"
     386             "#           avg unused memory per block:   %6u bytes\n"
     387             "\n"),
     388           g_cbAllocatedExpProgs, g_cBlocksAllocatedExpProgs, g_cbAllocatedExpProgs / g_cBlocksAllocatedExpProgs,
     389           g_cbUnusedMemExpProgs, (uint32_t)((uint64_t)g_cbUnusedMemExpProgs * 100 / g_cbAllocatedExpProgs),
     390           g_cbUnusedMemExpProgs / g_cBlocksAllocatedExpProgs);
     391
     392    printf(_("#   Total amount of block mem allocated: %8u bytes\n"), g_cbAllocated);
     393    printf(_("#       Total number of block allocated: %8u\n"), g_cBlockAllocated);
     394    printf(_("#                    Average block size: %8u byte\n"), g_cbAllocated / g_cBlockAllocated);
     395#endif
     396
     397    puts("");
     398}
     399
     400
     401/*
     402 *
     403 * Various utility functions.
     404 * Various utility functions.
     405 * Various utility functions.
     406 *
     407 */
     408
     409/**
     410 * Counts the number of dollar chars in the string.
     411 *
     412 * @returns Number of dollar chars.
     413 * @param   pchStr      The string to search (does not need to be zero
     414 *                      terminated).
     415 * @param   cchStr      The length of the string.
     416 */
     417static uint32_t kmk_cc_count_dollars(const char *pchStr, uint32_t cchStr)
     418{
     419    uint32_t cDollars = 0;
     420    const char *pch;
     421    while ((pch = memchr(pchStr, '$', cchStr)) != NULL)
     422    {
     423        cDollars++;
     424        cchStr -= pch - pchStr + 1;
     425        pchStr  = pch + 1;
     426    }
     427    return cDollars;
     428}
     429
     430#ifdef KMK_CC_STRICT
     431/**
     432 * Used to check that function arguments are left alone.
     433 * @returns Updated hash.
     434 * @param   uHash       The current hash value.
     435 * @param   psz         The string to hash.
     436 */
     437static uint32_t kmk_cc_debug_string_hash(uint32_t uHash, const char *psz)
     438{
     439    unsigned char ch;
     440    while ((ch = *(unsigned char const *)psz++) != '\0')
     441        uHash = (uHash << 6) + (uHash << 16) - uHash + (unsigned char)ch;
     442    return uHash;
     443}
     444
     445/**
     446 * Used to check that function arguments are left alone.
     447 * @returns Updated hash.
     448 * @param   uHash       The current hash value.
     449 * @param   pch         The string to hash, not terminated.
     450 * @param   cch         The number of chars to hash.
     451 */
     452static uint32_t kmk_cc_debug_string_hash_n(uint32_t uHash, const char *pch, uint32_t cch)
     453{
     454    while (cch-- > 0)
     455    {
     456        unsigned char ch = *(unsigned char const *)pch++;
     457        uHash = (uHash << 6) + (uHash << 16) - uHash + (unsigned char)ch;
     458    }
     459    return uHash;
     460}
     461
     462#endif
     463
     464
     465
     466/*
     467 *
     468 * The allocator.
     469 * The allocator.
     470 * The allocator.
     471 *
     472 */
     473
     474
     475/**
    333476 * For the first allocation using the block allocator.
    334477 *
    … …  
    349492     */
    350493    if (cbHint <= 512)
    351         cbBlock = 512;
     494    {
     495        if (cbHint <= 256)
     496            cbBlock = 128;
     497        else
     498            cbBlock = 256;
     499    }
    352500    else if (cbHint < 2048)
    353501        cbBlock = 1024;
    … …  
    366514    *ppBlockTail = pNewBlock;
    367515
     516#ifdef KMK_CC_WITH_STATS
     517    g_cBlockAllocated++;
     518    g_cbAllocated += cbBlock;
     519#endif
     520
    368521    return pNewBlock + 1;
    369522}
    … …  
    439592    *ppBlockTail = pNewBlock;
    440593
     594#ifdef KMK_CC_WITH_STATS
     595    g_cBlockAllocated++;
     596    g_cbAllocated += cbBlock;
     597#endif
     598
    441599    return pNewBlock + 1;
    442600}
    … …  
    506664
    507665    /* Figure the block size. */
    508     uint32_t cbBlock = pOldBlock->cbBlock;
     666    uint32_t cbBlock = !pOldBlock->pNext ? 128 : pOldBlock->cbBlock;
    509667    while (cbBlock - sizeof(KMKCCEXPJUMP) - sizeof(*pNewBlock) < cb)
    510668        cbBlock *= 2;
    … …  
    517675    *ppBlockTail = pNewBlock;
    518676
     677#ifdef KMK_CC_WITH_STATS
     678    g_cBlockAllocated++;
     679    g_cbAllocated += cbBlock;
     680#endif
     681
    519682    pRet = (PKMKCCEXPCORE)(pNewBlock + 1);
    520683
    … …  
    571734
    572735
    573 /**
    574  * Counts the number of dollar chars in the string.
    575  *
    576  * @returns Number of dollar chars.
    577  * @param   pchStr      The string to search (does not need to be zero
    578  *                      terminated).
    579  * @param   cchStr      The length of the string.
    580  */
    581 static uint32_t kmk_cc_count_dollars(const char *pchStr, uint32_t cchStr)
    582 {
    583     uint32_t cDollars = 0;
    584     const char *pch;
    585     while ((pch = memchr(pchStr, '$', cchStr)) != NULL)
    586     {
    587         cDollars++;
    588         cchStr -= pch - pchStr + 1;
    589         pchStr  = pch + 1;
    590     }
    591     return cDollars;
    592 }
     736/*
     737 *
     738 * The string expansion compiler.
     739 * The string expansion compiler.
     740 * The string expansion compiler.
     741 *
     742 */
    593743
    594744
    … …  
    622772        default:
    623773            return 0;
     774
     775        case 'e':
     776            if (!strcmp(pszFunction, "eval"))
     777                return 1;
     778            if (!strcmp(pszFunction, "evalctx"))
     779                return 1;
     780            return 0;
     781
    624782        case 'f':
    625             if (pszFunction[1] == 'i')
    626             {
    627                 if (!strcmp(pszFunction, "filter"))
    628                     return 1;
    629                 if (!strcmp(pszFunction, "filter-out"))
    630                     return 1;
    631             }
     783            if (!strcmp(pszFunction, "filter"))
     784                return 1;
     785            if (!strcmp(pszFunction, "filter-out"))
     786                return 1;
     787            if (!strcmp(pszFunction, "for"))
     788                return 1;
    632789            return 0;
     790
    633791        case 's':
    634792            if (!strcmp(pszFunction, "sort"))
    … …  
    12951453    PKMKCCBLOCK     pBlock;
    12961454    pProg = kmk_cc_block_alloc_first(&pBlock, sizeof(*pProg),
    1297                                      (kmk_cc_count_dollars(pchStr, cchStr) + 8)  * 16);
     1455                                     (kmk_cc_count_dollars(pchStr, cchStr) + 4)  * 8);
    12981456    if (pProg)
    12991457    {
    … …  
    13031461        pProg->pFirstInstr  = (PKMKCCEXPCORE)kmk_cc_block_get_next_ptr(pBlock);
    13041462        kmk_cc_exp_stats_init(&pProg->Stats);
     1463#ifdef KMK_CC_STRICT
     1464        pProg->uInputHash   = kmk_cc_debug_string_hash_n(0, pchStr, cchStr);
     1465#endif
    13051466
    13061467        /*
    … …  
    13081469         */
    13091470        if (kmk_cc_exp_compile_common(&pProg->pBlockTail, pchStr, cchStr) == 0)
     1471        {
     1472#ifdef KMK_CC_WITH_STATS
     1473            pBlock = pProg->pBlockTail;
     1474            if (!pBlock->pNext)
     1475                g_cSingleBlockExpProgs++;
     1476            else if (!pBlock->pNext->pNext)
     1477                g_cTwoBlockExpProgs++;
     1478            else
     1479                g_cMultiBlockExpProgs++;
     1480            for (; pBlock; pBlock = pBlock->pNext)
     1481            {
     1482                g_cBlocksAllocatedExpProgs++;
     1483                g_cbAllocatedExpProgs += pBlock->cbBlock;
     1484                g_cbUnusedMemExpProgs += pBlock->cbBlock - pBlock->offNext;
     1485            }
     1486#endif
    13101487            return pProg;
     1488        }
    13111489        kmk_cc_block_free_list(pProg->pBlockTail);
    13121490    }
    13131491    return NULL;
    13141492}
    1315 
    13161493
    13171494
    … …  
    13251502{
    13261503    return NULL;
     1504}
     1505
     1506
     1507/**
     1508 * Updates the recursive_without_dollar member of a variable structure.
     1509 *
     1510 * This avoid compiling string expansion programs without only a CopyString
     1511 * instruction.  By setting recursive_without_dollar to 1, code calling
     1512 * kmk_cc_compile_variable_for_expand and kmk_exec_expand_to_var_buf will
     1513 * instead treat start treating it as a simple variable, which is faster.
     1514 *
     1515 * @returns The updated recursive_without_dollar value.
     1516 * @param   pVar        Pointer to the variable.
     1517 */
     1518static int kmk_cc_update_variable_recursive_without_dollar(struct variable *pVar)
     1519{
     1520    int fValue;
     1521    KMK_CC_ASSERT(pVar->recursive_without_dollar == 0);
     1522
     1523    if (memchr(pVar->value, '$', pVar->value_length))
     1524        fValue = -1;
     1525    else
     1526        fValue = 1;
     1527    pVar->recursive_without_dollar = fValue;
     1528
     1529    return fValue;
    13271530}
    13281531
    … …  
    13371540struct kmk_cc_expandprog *kmk_cc_compile_variable_for_expand(struct variable *pVar)
    13381541{
     1542    KMK_CC_ASSERT(strlen(pVar->value) == pVar->value_length);
    13391543    KMK_CC_ASSERT(!pVar->expandprog);
     1544    KMK_CC_ASSERT(pVar->recursive_without_dollar <= 0);
     1545
    13401546    if (   !pVar->expandprog
    1341         && pVar->value_length > 0
    13421547        && pVar->recursive)
    13431548    {
    1344         KMK_CC_ASSERT(strlen(pVar->value) == pVar->value_length);
    1345         pVar->expandprog = kmk_cc_exp_compile(pVar->value, pVar->value_length);
     1549        if (   pVar->recursive_without_dollar < 0
     1550            || (   pVar->recursive_without_dollar == 0
     1551                && kmk_cc_update_variable_recursive_without_dollar(pVar) < 0) )
     1552        {
     1553            pVar->expandprog = kmk_cc_exp_compile(pVar->value, pVar->value_length);
     1554            g_cVarForExpandCompilations++;
     1555        }
    13461556    }
    13471557    return pVar->expandprog;
    13481558}
    1349 
    1350 
    1351 #ifndef NDEBUG
    1352 /**
    1353  * Used to check that function arguments are left alone.
    1354  * @returns Updated hash.
    1355  * @param   uHash       The current hash value.
    1356  * @param   psz         The string to hash.
    1357  */
    1358 static uint32_t kmk_exec_debug_string_hash(uint32_t uHash, const char *psz)
    1359 {
    1360     unsigned char ch;
    1361     while ((ch = *(unsigned char const *)psz++) != '\0')
    1362         uHash = (uHash << 6) + (uHash << 16) - uHash + (unsigned char)ch;
    1363     return uHash;
    1364 }
    1365 #endif
    13661559
    13671560
    … …  
    13771570    if (pVar->value_length > 0)
    13781571    {
    1379         if (!pVar->recursive)
     1572        if (!pVar->recursive || IS_VARIABLE_RECURSIVE_WITHOUT_DOLLAR(pVar))
    13801573            pchDst = variable_buffer_output(pchDst, pVar->value, pVar->value_length);
    13811574        else
    … …  
    15271720                if (!pInstr->Core.fDirty)
    15281721                {
    1529 #ifndef NDEBUG
     1722#ifdef KMK_CC_STRICT
    15301723                    uint32_t uCrcBefore = 0;
    15311724                    uint32_t uCrcAfter = 0;
    15321725                    iArg = pInstr->Core.cArgs;
    15331726                    while (iArg-- > 0)
    1534                         uCrcBefore = kmk_exec_debug_string_hash(uCrcBefore, pInstr->apszArgs[iArg]);
     1727                        uCrcBefore = kmk_cc_debug_string_hash(uCrcBefore, pInstr->apszArgs[iArg]);
    15351728#endif
    15361729
    15371730                    pchDst = pInstr->Core.pfnFunction(pchDst, (char **)&pInstr->apszArgs[0], pInstr->Core.pszFuncName);
    15381731
    1539 #ifndef NDEBUG
     1732#ifdef KMK_CC_STRICT
    15401733                    iArg = pInstr->Core.cArgs;
    15411734                    while (iArg-- > 0)
    1542                         uCrcAfter = kmk_exec_debug_string_hash(uCrcAfter, pInstr->apszArgs[iArg]);
     1735                        uCrcAfter = kmk_cc_debug_string_hash(uCrcAfter, pInstr->apszArgs[iArg]);
    15431736                    KMK_CC_ASSERT(uCrcBefore == uCrcAfter);
    15441737#endif
    … …  
    15751768                if (!pInstr->Core.fDirty)
    15761769                {
    1577 #ifndef NDEBUG
     1770#ifdef KMK_CC_STRICT
    15781771                    uint32_t    uCrcBefore = 0;
    15791772                    uint32_t    uCrcAfter = 0;
    … …  
    15901783                        papszArgsShadow[iArg] = pszArg;
    15911784                        papszArgs[iArg]       = pszArg;
    1592 #ifndef NDEBUG
    1593                         uCrcBefore = kmk_exec_debug_string_hash(uCrcBefore, pszArg);
     1785#ifdef KMK_CC_STRICT
     1786                        uCrcBefore = kmk_cc_debug_string_hash(uCrcBefore, pszArg);
    15941787#endif
    15951788                    }
    … …  
    15991792                    while (iArg-- > 0)
    16001793                    {
    1601 #ifndef NDEBUG
     1794#ifdef KMK_CC_STRICT
    16021795                        KMK_CC_ASSERT(papszArgsShadow[iArg] == papszArgs[iArg]);
    1603                         uCrcAfter = kmk_exec_debug_string_hash(uCrcAfter, papszArgsShadow[iArg]);
     1796                        uCrcAfter = kmk_cc_debug_string_hash(uCrcAfter, papszArgsShadow[iArg]);
    16041797#endif
    16051798                        if (!pInstr->aArgs[iArg].fPlain)
    … …  
    17331926    cchResult -= offStart;
    17341927    kmk_cc_exp_stats_update(&pProg->Stats, cchResult);
     1928    g_cVarForExpandExecs++;
    17351929
    17361930    return pchDst;
    … …  
    17601954{
    17611955    KMK_CC_ASSERT(pVar->expandprog);
     1956    KMK_CC_ASSERT(pVar->expandprog->uInputHash == kmk_cc_debug_string_hash(0, pVar->value));
    17621957    return kmk_exec_expand_prog_to_var_buf(pVar->expandprog, pchDst);
    17631958}
Note: See TracChangeset for help on using the changeset viewer.