Re: atomic-free allocator

On 29 янв, 23:01, Dmitriy Vyukov <dvyu...@xxxxxxxxx> wrote:
Multi-threaded memory allocator w/o atomic RMW operations or heavy
memory barriers. At all.
Basic outline:
Allocator created per thread. Local free operations use simple stack.
Remote free operations use mpsc-stack but with "hazard_cas" - cmpxchg
w/o lock prefix. So this mpsc-stack used only as "hint" - I assume
that I can find in this stack some nodes twice, and some nodes can
lost. To resurrect lost nodes I use "repair" operation. Repair simply
scan all nodes and search for lost nodes.


Main question - what will be loss rate (i.e. when hazard_cas() succeed
but node is not actually enqueued into stack). If loss rate is high
then we have to frequently repair block, to not lose too many nodes.
If loss rate is low than we can repair block rarely. Repair is
relatively expensive operation.

I test the allocator under sufficiently heavy load. On dual-core Intel
with shared L2 cache loss rate is about 0.01%, i.e. 1 lost node per
10000 successfully transfered nodes. So if I want to lose no more than
10 nodes, I can repair 1 time for every 100000 successful remote node
free() operations. I think it's very good results.
On quad-core Intel with 2 separete L2 caches loss rate is about 1%,
i.e. 1 lost node per 100 successfully transfered nodes. So if I want
to lose no more than 10 nodes, I can repair 1 time for every 1000
successful remote node free() operations. It's not so good.

So I think hybrid approach can be used.
For example. System with 2 processors and 8 hardware threads per
processor. hazard remote free operations can be used inside processor,
and accurate (with lock prefix) remote free operations can be used
between processors. So allocator will have 3 anchors - 1 for local
free, 1 for hazard remote free and 1 for accurate very remote free.


Dmitriy V'jukov
.

Relevant Pages

  • new connection wizard
    ... IP stack and almost all my services were set to manual. ... Windows XP machine available, you can find a list of ... >My computer got a virus so after having to repair ... >setup it had wiped my internet connection so having gone ...
    (microsoft.public.windowsxp.network_web)
  • Update #1 - Initialization Failure on Running Apps...
    ... I'm having real problems after updating. ... If I then terminate the program, build and re-run I get the same "failed to initialize" message but the call stack is gives: ... The next thing to rule out is that my update was somehow corrupted so I'm going to try is to repair with the "delete install cache" checked. ... I'll then repair again and I'm hoping that it'll download a fresh update. ...
    (borland.public.delphi.non-technical)
  • Re: ***VERY DIFFICULT SOLUTION NEEDED***
    ... > While using some anti-spam software I accidentally ... stack after removing one of the components that is part of the malware. ... Or you can download and run LSPfix, tell it "I know what I am ... Only repair the stack if the tool indicates that the stack ...
    (microsoft.public.windowsxp.network_web)