VirtualBox

Changeset 26452 in vbox for trunk/src/VBox/Runtime


Ignore:
Timestamp:
Feb 11, 2010 6:41:06 PM (15 years ago)
Author:
vboxsync
svn:sync-xref-src-repo-rev:
57599
Message:

iprt/memcache.h: Some more optimizations and more benchmarks.

Location:
trunk/src/VBox/Runtime
Files:
2 edited

Legend:

Unmodified
Added
Removed

  • trunk/src/VBox/Runtime/common/alloc/memcache.cpp

    r26428 r26452  
    5353/** Pointer to a cache page. */
    5454typedef struct RTMEMCACHEPAGE *PRTMEMCACHEPAGE;
     55
     56
     57
     58/**
     59 * A free object.
     60 *
     61 * @remarks This only works if the objects don't have a constructor or
     62 *          destructor and are big enough.
     63 */
     64typedef struct RTMEMCACHEFREEOBJ
     65{
     66    /** Pointer to the next free object  */
     67    struct RTMEMCACHEFREEOBJ * volatile pNext;
     68} RTMEMCACHEFREEOBJ;
     69/** Pointer to a free object. */
     70typedef RTMEMCACHEFREEOBJ *PRTMEMCACHEFREEOBJ;
    5571
    5672
    … …  
    107123    /** The maximum number of objects. */
    108124    uint32_t                    cMax;
     125    /** Whether to the use the free list or not. */
     126    bool                        fUseFreeList;
    109127    /** Head of the page list. */
    110128    PRTMEMCACHEPAGE             pPageHead;
    … …  
    124142    /** This may point to a page with free entries. */
    125143    PRTMEMCACHEPAGE volatile    pPageHint;
     144    /** Stack of free items.
     145     * These are marked as used in the allocation bitmaps.
     146     *
     147     * @todo This doesn't scale well when several threads are beating on the
     148     *       cache.  Also, it totally doesn't work when we've got a
     149     *       constructor/destructor around or the objects are too small. */
     150    PRTMEMCACHEFREEOBJ volatile pFreeTop;
    126151} RTMEMCACHEINT;
    127152
    … …  
    129154
    130155RTDECL(int) RTMemCacheCreate(PRTMEMCACHE phMemCache, size_t cbObject, size_t cbAlignment, uint32_t cMaxObjects,
    131                              PFNMEMCACHECTOR pfnCtor, PFNMEMCACHEDTOR pfnDtor, void *pvUser)
     156                             PFNMEMCACHECTOR pfnCtor, PFNMEMCACHEDTOR pfnDtor, void *pvUser, uint32_t fFlags)
     157
    132158{
    133159    AssertPtr(phMemCache);
    134160    AssertPtrNull(pfnCtor);
    135161    AssertPtrNull(pfnDtor);
     162    AssertReturn(!pfnDtor || pfnCtor, VERR_INVALID_PARAMETER);
    136163    AssertReturn(cbObject > 0, VERR_INVALID_PARAMETER);
    137164    AssertReturn(cbObject <= PAGE_SIZE / 8, VERR_INVALID_PARAMETER);
     165    AssertReturn(!fFlags, VERR_INVALID_PARAMETER);
    138166
    139167    if (cbAlignment == 0)
    … …  
    173201    pThis->cBits            = RT_ALIGN(pThis->cPerPage, 64);
    174202    pThis->cMax             = cMaxObjects;
    175     pThis->cTotal           = 0;
    176     pThis->cFree            = 0;
     203    pThis->fUseFreeList     = cbObject >= sizeof(RTMEMCACHEFREEOBJ)
     204                           && !pfnCtor
     205                           && !pfnDtor;
    177206    pThis->pPageHead        = NULL;
    178     pThis->pPageHint        = NULL;
    179207    pThis->pfnCtor          = pfnCtor;
    180208    pThis->pfnDtor          = pfnDtor;
    181209    pThis->pvUser           = pvUser;
     210    pThis->cTotal           = 0;
     211    pThis->cFree            = 0;
     212    pThis->pPageHint        = NULL;
     213    pThis->pFreeTop         = NULL;
    182214
    183215    *phMemCache = pThis;
    … …  
    193225    AssertPtrReturn(pThis, VERR_INVALID_HANDLE);
    194226    AssertReturn(pThis->u32Magic == RTMEMCACHE_MAGIC, VERR_INVALID_HANDLE);
    195     AssertMsg((uint32_t)pThis->cFree == pThis->cTotal, ("cFree=%u cTotal=%u\n", pThis->cFree, pThis->cTotal));
     227#ifdef RT_STRICT
     228    uint32_t cFree = pThis->cFree;
     229    for (PRTMEMCACHEFREEOBJ pFree = pThis->pFreeTop; pFree; pFree = pFree->pNext)
     230        cFree++;
     231    AssertMsg(cFree == pThis->cTotal, ("cFree=%u cTotal=%u\n", cFree, pThis->cTotal));
     232#endif
    196233
    197234    /*
    … …  
    268305            pb = (uint8_t *)((uintptr_t)pb & ~(uintptr_t)7);
    269306            pPage->pbmAlloc     = pb;
    270             Assert((uintptr_t)pPage->pbmCtor + pThis->cBits / 8 < (uintptr_t)pPage->pbmCtor);
     307            Assert((uintptr_t)pPage->pbmCtor + pThis->cBits / 8 <= (uintptr_t)pPage->pbmAlloc);
    271308
    272309            /* Mark the bitmap padding and any unused objects as allocated. */
    … …  
    322359    AssertPtrReturn(pThis, VERR_INVALID_PARAMETER);
    323360    AssertReturn(pThis->u32Magic == RTMEMCACHE_MAGIC, VERR_INVALID_PARAMETER);
     361
     362    /*
     363     * Try grab a free object from the stack.
     364     */
     365    PRTMEMCACHEFREEOBJ pObj = (PRTMEMCACHEFREEOBJ)ASMAtomicUoReadPtr((void * volatile *)&pThis->pFreeTop);
     366    if (pObj)
     367    {
     368        PRTMEMCACHEFREEOBJ pNext;
     369        do
     370        {
     371            pNext = (PRTMEMCACHEFREEOBJ)ASMAtomicUoReadPtr((void * volatile *)&pObj->pNext);
     372            if (ASMAtomicCmpXchgPtr((void * volatile *)&pThis->pFreeTop, pNext, pObj))
     373            {
     374                *ppvObj = pObj;
     375                return VINF_SUCCESS;
     376            }
     377            pObj = (PRTMEMCACHEFREEOBJ)ASMAtomicUoReadPtr((void * volatile *)&pThis->pFreeTop);
     378        } while (pObj);
     379    }
    324380
    325381    /*
    … …  
    438494    Assert(RT_ALIGN_P(pvObj, pThis->cbAlignment) == pvObj);
    439495
    440     /* Note: Do *NOT* attempt to poison the object if we have a constructor
    441              or/and destructor! */
    442 
    443     /*
    444      * Find the cache page.  The page structure is at the start of the page.
    445      */
    446     PRTMEMCACHEPAGE pPage = (PRTMEMCACHEPAGE)(((uintptr_t)pvObj) & ~(uintptr_t)PAGE_OFFSET_MASK);
    447     Assert(pPage->pCache == pThis);
    448     Assert(ASMAtomicUoReadS32(&pPage->cFree) < (int32_t)pThis->cPerPage);
    449 
    450     /*
    451      * Clear the bitmap bit and update the two object counter. Order matters!
    452      */
    453     uintptr_t offObj = (uintptr_t)pvObj - (uintptr_t)pPage->pbObjects;
    454     uintptr_t iObj   = offObj / pThis->cbObject;
    455     Assert(iObj * pThis->cbObject == offObj);
    456     Assert(iObj < pThis->cPerPage);
    457     AssertReturnVoid(ASMAtomicBitTestAndClear(pPage->pbmAlloc, iObj));
    458 
    459     ASMAtomicIncS32(&pPage->cFree);
    460     ASMAtomicIncS32(&pThis->cFree);
    461 }
    462 
     496    if (pThis->fUseFreeList)
     497    {
     498# ifdef RT_STRICT
     499        /* This is the same as the other branch, except it's not actually freed. */
     500        PRTMEMCACHEPAGE pPage = (PRTMEMCACHEPAGE)(((uintptr_t)pvObj) & ~(uintptr_t)PAGE_OFFSET_MASK);
     501        Assert(pPage->pCache == pThis);
     502        Assert(ASMAtomicUoReadS32(&pPage->cFree) < (int32_t)pThis->cPerPage);
     503        uintptr_t offObj = (uintptr_t)pvObj - (uintptr_t)pPage->pbObjects;
     504        uintptr_t iObj   = offObj / pThis->cbObject;
     505        Assert(iObj * pThis->cbObject == offObj);
     506        Assert(iObj < pThis->cPerPage);
     507        AssertReturnVoid(ASMBitTest(pPage->pbmAlloc, iObj));
     508# endif
     509
     510        /*
     511         * Push it onto the free stack.
     512         */
     513        PRTMEMCACHEFREEOBJ pObj = (PRTMEMCACHEFREEOBJ)pvObj;
     514        PRTMEMCACHEFREEOBJ pNext;
     515        do
     516        {
     517            pNext = (PRTMEMCACHEFREEOBJ)ASMAtomicUoReadPtr((void * volatile *)&pThis->pFreeTop);
     518            pObj->pNext = pNext;
     519        } while (!ASMAtomicCmpXchgPtr((void * volatile *)&pThis->pFreeTop, pObj, pNext));
     520    }
     521    else
     522    {
     523        /* Note: Do *NOT* attempt to poison the object if we have a constructor
     524                 or/and destructor! */
     525
     526        /*
     527         * Find the cache page.  The page structure is at the start of the page.
     528         */
     529        PRTMEMCACHEPAGE pPage = (PRTMEMCACHEPAGE)(((uintptr_t)pvObj) & ~(uintptr_t)PAGE_OFFSET_MASK);
     530        Assert(pPage->pCache == pThis);
     531        Assert(ASMAtomicUoReadS32(&pPage->cFree) < (int32_t)pThis->cPerPage);
     532
     533        /*
     534         * Clear the bitmap bit and update the two object counter. Order matters!
     535         */
     536        uintptr_t offObj = (uintptr_t)pvObj - (uintptr_t)pPage->pbObjects;
     537        uintptr_t iObj   = offObj / pThis->cbObject;
     538        Assert(iObj * pThis->cbObject == offObj);
     539        Assert(iObj < pThis->cPerPage);
     540        AssertReturnVoid(ASMAtomicBitTestAndClear(pPage->pbmAlloc, iObj));
     541
     542        ASMAtomicIncS32(&pPage->cFree);
     543        ASMAtomicIncS32(&pThis->cFree);
     544    }
     545}
     546

  • trunk/src/VBox/Runtime/testcase/tstRTMemCache.cpp

    r26420 r26452  
    3636#include <iprt/asm.h>
    3737#include <iprt/err.h>
     38#include <iprt/cache.h>
    3839#include <iprt/initterm.h>
    3940#include <iprt/mem.h>
    … …  
    5758    uint32_t            cbObject;
    5859    bool                fUseCache;
     60    bool                fUseOldCache;
    5961} TST3THREAD, *PTST3THREAD;
    6062
    … …  
    6769/** Global mem cache handle for use in some of the testcases. */
    6870static RTMEMCACHE           g_hMemCache;
     71/** For testcase 3. */
     72static PRTOBJCACHE          g_pOldCacheTst3;
    6973/** Stop indicator for tst3 threads.  */
    7074static bool volatile        g_fTst3Stop;
    … …  
    8286    uint32_t const cObjects = PAGE_SIZE * 2 / 256;
    8387    RTMEMCACHE hMemCache;
    84     RTTESTI_CHECK_RC_RETV(RTMemCacheCreate(&hMemCache, 256, cObjects, 32, NULL, NULL, NULL), VINF_SUCCESS);
     88    RTTESTI_CHECK_RC_RETV(RTMemCacheCreate(&hMemCache, 256, cObjects, 32, NULL, NULL, NULL, 0 /*fFlags*/), VINF_SUCCESS);
    8589    RTTESTI_CHECK_RETV(hMemCache != NIL_RTMEMCACHE);
    8690
    … …  
    163167    bool            fFail    = false;
    164168    uint32_t const  cObjects = PAGE_SIZE * 2 / 256;
    165     RTTESTI_CHECK_RC_RETV(RTMemCacheCreate(&g_hMemCache, 256, cObjects, 32, tst2Ctor, tst2Dtor, &fFail), VINF_SUCCESS);
     169    RTTESTI_CHECK_RC_RETV(RTMemCacheCreate(&g_hMemCache, 256, cObjects, 32, tst2Ctor, tst2Dtor, &fFail, 0 /*fFlags*/), VINF_SUCCESS);
    166170
    167171    /* A failure run first. */
    … …  
    208212{
    209213    PTST3THREAD     pThread     = (PTST3THREAD)(pvArg);
    210     bool            fUseCache   = pThread->fUseCache;
    211214    size_t          cbObject    = pThread->cbObject;
    212215    uint64_t        cIterations = 0;
    … …  
    216219
    217220    /* allocate and free loop */
    218     while (!g_fTst3Stop)
    219     {
    220         void *apv[64];
    221 
    222         if (fUseCache)
    223         {
     221    if (pThread->fUseCache)
     222    {
     223        while (!g_fTst3Stop)
     224        {
     225            void *apv[64];
    224226            for (unsigned i = 0; i < RT_ELEMENTS(apv); i++)
    225227            {
    … …  
    229231            for (unsigned i = 0; i < RT_ELEMENTS(apv); i++)
    230232                RTMemCacheFree(g_hMemCache, apv[i]);
    231         }
    232         else
    233         {
     233
     234            cIterations += RT_ELEMENTS(apv);
     235        }
     236    }
     237    else if (pThread->fUseOldCache)
     238    {
     239        while (!g_fTst3Stop)
     240        {
     241            void *apv[64];
     242
     243            for (unsigned i = 0; i < RT_ELEMENTS(apv); i++)
     244            {
     245                apv[i] = NULL;
     246                RTTEST_CHECK_RC_OK(g_hTest, RTCacheRequest(g_pOldCacheTst3, &apv[i]));
     247            }
     248
     249            for (unsigned i = 0; i < RT_ELEMENTS(apv); i++)
     250                RTCacheInsert(g_pOldCacheTst3, apv[i]);
     251
     252            cIterations += RT_ELEMENTS(apv);
     253        }
     254    }
     255    else
     256    {
     257        while (!g_fTst3Stop)
     258        {
     259            void *apv[64];
     260
    234261            for (unsigned i = 0; i < RT_ELEMENTS(apv); i++)
    235262            {
    … …  
    240267            for (unsigned i = 0; i < RT_ELEMENTS(apv); i++)
    241268                RTMemFree(apv[i]);
    242         }
    243         cIterations += RT_ELEMENTS(apv);
     269
     270            cIterations += RT_ELEMENTS(apv);
     271        }
    244272    }
    245273
    … …  
    252280 * Time constrained test with and unlimited  N threads.
    253281 */
    254 static void tst3(uint32_t cThreads, uint32_t cbObject, bool fUseCache, uint32_t cSecs)
    255 {
    256     RTTestISubF("Benchmark - %u threads, %u bytes, %u secs, %s", cThreads, cbObject, cSecs, fUseCache ? "RTMemCache" : "RTMemAlloc");
     282static void tst3(uint32_t cThreads, uint32_t cbObject, int iMethod, uint32_t cSecs)
     283{
     284    RTTestISubF("Benchmark - %u threads, %u bytes, %u secs, %s", cThreads, cbObject, cSecs,
     285                iMethod == 0 ? "RTMemCache"
     286                : iMethod == 1 ? "RTCache"
     287                : "RTMemAlloc");
    257288
    258289    /*
    … …  
    260291     * the threads.
    261292     */
    262     RTTESTI_CHECK_RC_RETV(RTMemCacheCreate(&g_hMemCache, cbObject, 0 /*cbAlignment*/, UINT32_MAX, NULL, NULL, NULL), VINF_SUCCESS);
     293    RTTESTI_CHECK_RC_RETV(RTMemCacheCreate(&g_hMemCache, cbObject, 0 /*cbAlignment*/, UINT32_MAX, NULL, NULL, NULL, 0 /*fFlags*/), VINF_SUCCESS);
     294    RTTESTI_CHECK_RC_RETV(RTCacheCreate(&g_pOldCacheTst3, 0, cbObject, RTOBJCACHE_PROTECT_INSERT | RTOBJCACHE_PROTECT_REQUEST), VINF_SUCCESS);
    263295
    264296    RTSEMEVENTMULTI hEvt;
    … …  
    273305        aThreads[i].hThread     = NIL_RTTHREAD;
    274306        aThreads[i].cIterations = 0;
    275         aThreads[i].fUseCache   = fUseCache;
     307        aThreads[i].fUseCache   = iMethod == 0;
     308        aThreads[i].fUseOldCache= iMethod == 1;
    276309        aThreads[i].cbObject    = cbObject;
    277310        aThreads[i].hEvt        = hEvt;
    … …  
    305338
    306339    /* clean up */
     340    RTTESTI_CHECK_RC(RTCacheDestroy(g_pOldCacheTst3), VINF_SUCCESS);
    307341    RTTESTI_CHECK_RC(RTMemCacheDestroy(g_hMemCache), VINF_SUCCESS);
    308342    RTTESTI_CHECK_RC_OK(RTSemEventMultiDestroy(hEvt));
    309343}
    310344
    311 int main()
     345static void tst3AllMethods(uint32_t cThreads, uint32_t cbObject, uint32_t cSecs)
     346{
     347    tst3(cThreads, cbObject, 0, cSecs);
     348    tst3(cThreads, cbObject, 1, cSecs);
     349    tst3(cThreads, cbObject, 2, cSecs);
     350}
     351
     352
     353int main(int argc, char **argv)
    312354{
    313355    RTTEST hTest;
    … …  
    322364    if (RTTestIErrorCount() == 0)
    323365    {
    324         /*  threads, cbObj, fUseCache, cSecs */
    325         tst3(     1,   256,      true,     5);
    326         tst3(     1,   256,     false,     5);
    327         tst3(     1,    32,      true,     5);
    328         tst3(     1,    32,     false,     5);
    329         tst3(     1,     8,      true,     5);
    330         tst3(     1,     8,     false,     5);
    331         tst3(     1,     2,      true,     5);
    332         tst3(     1,     2,     false,     5);
    333         tst3(     1,     1,      true,     5);
    334         tst3(     1,     1,     false,     5);
    335 
    336         tst3(     3,   256,      true,     5);
    337         tst3(     3,   256,     false,     5);
    338         tst3(     3,   128,      true,     5);
    339         tst3(     3,   128,     false,     5);
    340         tst3(     3,    64,      true,     5);
    341         tst3(     3,    64,     false,     5);
    342         tst3(     3,    32,      true,     5);
    343         tst3(     3,    32,     false,     5);
    344         tst3(     3,     2,      true,     5);
    345         tst3(     3,     2,     false,     5);
    346         tst3(     3,     1,      true,     5);
    347         tst3(     3,     1,     false,     5);
    348 
    349         tst3(    16,    32,      true,     5);
    350         tst3(    16,    32,     false,     5);
     366        uint32_t cSecs = argc == 1 ? 5 : 2;
     367        /*            threads, cbObj, cSecs */
     368        tst3AllMethods(     1,   256, cSecs);
     369        tst3AllMethods(     1,    32, cSecs);
     370        tst3AllMethods(     1,     8, cSecs);
     371        tst3AllMethods(     1,     2, cSecs);
     372        tst3AllMethods(     1,     1, cSecs);
     373
     374        tst3AllMethods(     3,   256, cSecs);
     375        tst3AllMethods(     3,   128, cSecs);
     376        tst3AllMethods(     3,    64, cSecs);
     377        tst3AllMethods(     3,    32, cSecs);
     378        tst3AllMethods(     3,     2, cSecs);
     379        tst3AllMethods(     3,     1, cSecs);
     380
     381        tst3AllMethods(    16,    32, cSecs);
    351382    }
    352383
Note: See TracChangeset for help on using the changeset viewer.

© 2025 Oracle Support Privacy / Do Not Sell My Info Terms of Use Trademark Policy Automated Access Etiquette