Home » Community » Coffee corner » C++ FQA
Re: C++ FQA [message #12685 is a reply to message #12613] |
Tue, 13 November 2007 01:56 |
Zardos
Messages: 62 Registered: April 2007
|
Member |
|
|
luzr wrote on Sat, 10 November 2007 17:54 |
cbpporter wrote on Sat, 10 November 2007 11:31 |
And I'm quite surprised to see people who don't like gc, but have nothing against reference counting, which is slower and almost impossible to use efficiently in a multi-threading application.
|
I mostly agree with this...
Mirek
|
If we talk about a naive reference counting implementation I agree without hestiation.
About the prejudice: "GC is fast" / "Reference counting is slow":
I have read 3 papers approximately one year ago which showed reference counting can be as fast as garbage collection. In addition there are some benefits. Unfortunately I don't have the links anymore. But you may try goolgle with something like "cycles reference counting" and read the /newer/ papers!
But some basic ideas I still remember:
1.) Aggressive removal of AddRef/RemRef by a static flow analysis of the programm: The idea is to only inc. or dec. reference counters if neccessary. Usually only if a (smart)pointer manipulation is done inside a struct/class/... It is not neccessary to do inc./dec. operation for (smart)pointers on the stack or as function arguments. Probably special care has to be taken for threads. Even for (smart)pointers inside structs many inc./dec. operation can be elimanated by a (not so complicated) static analysis of the programm flow.
2.) Avoiding "Atmoic operations": The simple but effective idea is this. Instead of doing AtmoicInc/AtomicDec operations directly on the refence counters all Increments and Decrements are logged in a buffer with a fixed length. Each thread has it's own buffers! So, no locks are required for the ordinary Inc/Dec. If the buffer is full the buffer is given to a "memory management" thread. This requires a Lock operation, but if we assume a buffer has place for 10000 "Inc/Dec" ops. the synchronization cost boils down to 1/10000 which is negligible.
The memory management thraed finally can perform the inc/dec operations without the expensive "Atmoic" vesions just ordinary ++/--
Benefit: The memory management thread can be tuned to only do a fixed number of delete operations per second. This avoids "cascading deletes" where one destructer call triggers a chain of delete operations. => Even with manual memory management there can be stalls!
=> So we have a concurent - nearly log free - reference counting garbage collection.
3.) Cycles: I have forgotten how they get removed. But it was not to complicated to understand. Yes it costs time to detect the cycles... The cost is reduced by point 1.). In addition the cylcle detection can be performed by the memory management - concurrently - without any additional locks. And again this memory management can be tuned to do only N. operations per second. To really spread the memory mangament cost over time (Of course, this means for some time periods more memory is allocated than necessary).
I think it's a really interesting topic. I always had the feeling Refernce Counting can be supperior over garbage collection... May be the furture brings a revival of the counters....
EDIT: I think 2.) was implemented differently: Instead of having buffer with a fixed length: The memory management thraed performed a "stop the world" (pausing all threads) periodically and fetched the buffers from all running threads. While stop the world sounds like stalling - you have to remember only some pointers to buffers have to be transfered to the menory management thread... After the transfer the world starts rotating again.
[Updated on: Tue, 13 November 2007 02:18] Report message to a moderator
|
|
|
|
|
C++ FQA
By: unodgs on Tue, 06 November 2007 23:27
|
|
|
Re: C++ FQA
|
|
|
Re: C++ FQA
By: unodgs on Wed, 07 November 2007 10:40
|
|
|
Re: C++ FQA
|
|
|
Re: C++ FQA
By: unodgs on Wed, 07 November 2007 13:15
|
|
|
Re: C++ FQA
|
|
|
Re: C++ FQA
|
|
|
Re: C++ FQA
|
|
|
Re: C++ FQA
|
|
|
Re: C++ FQA
|
|
|
Re: C++ FQA
By: mirek on Thu, 08 November 2007 05:34
|
|
|
Re: C++ FQA
By: Zardos on Thu, 08 November 2007 13:33
|
|
|
Re: C++ FQA
By: mirek on Thu, 08 November 2007 19:25
|
|
|
Re: C++ FQA
By: mdelfede on Thu, 08 November 2007 23:39
|
|
|
Re: C++ FQA
By: mirek on Fri, 09 November 2007 08:51
|
|
|
Re: C++ FQA
By: mdelfede on Fri, 09 November 2007 13:41
|
|
|
Re: C++ FQA
By: mirek on Fri, 09 November 2007 14:48
|
|
|
Re: C++ FQA
By: mdelfede on Fri, 09 November 2007 15:52
|
|
|
Re: C++ FQA
By: waxblood on Fri, 09 November 2007 17:07
|
|
|
Re: C++ FQA
By: mdelfede on Fri, 09 November 2007 19:51
|
|
|
Re: C++ FQA
By: mirek on Sat, 10 November 2007 15:14
|
|
|
Re: C++ FQA
By: mdelfede on Sat, 10 November 2007 17:06
|
|
|
Re: C++ FQA
|
|
|
Re: C++ FQA
By: mirek on Sat, 10 November 2007 17:54
|
|
|
Re: C++ FQA
By: mdelfede on Sat, 10 November 2007 23:57
|
|
|
Re: C++ FQA
By: mirek on Sun, 11 November 2007 09:54
|
|
|
Re: C++ FQA
By: mdelfede on Sun, 11 November 2007 11:25
|
|
|
Re: C++ FQA
By: Zardos on Tue, 13 November 2007 01:56
|
|
|
Re: C++ FQA
By: mirek on Tue, 13 November 2007 09:25
|
|
|
Re: C++ FQA
|
|
|
Re: C++ FQA
By: mirek on Tue, 13 November 2007 10:52
|
|
|
Re: C++ FQA
By: mirek on Thu, 22 November 2007 05:43
|
|
|
Re: C++ FQA
By: mdelfede on Sun, 11 November 2007 11:36
|
|
|
Re: C++ FQA
|
|
|
Re: C++ FQA
By: mdelfede on Sun, 11 November 2007 18:52
|
|
|
Re: C++ FQA
|
|
|
Re: C++ FQA
By: mirek on Mon, 12 November 2007 09:46
|
|
|
Re: C++ FQA
By: mdelfede on Mon, 12 November 2007 10:19
|
|
|
Re: C++ FQA
|
|
|
Re: C++ FQA
By: mdelfede on Mon, 12 November 2007 11:43
|
|
|
Re: C++ FQA
|
|
|
Re: C++ FQA
By: mdelfede on Mon, 12 November 2007 16:47
|
|
|
Re: C++ FQA
|
|
|
Re: C++ FQA
By: mirek on Mon, 12 November 2007 20:15
|
|
|
Re: C++ FQA
By: mirek on Mon, 12 November 2007 20:21
|
|
|
Re: C++ FQA
|
|
|
Re: C++ FQA
By: mirek on Mon, 12 November 2007 22:43
|
|
|
Re: C++ FQA
|
|
|
Re: C++ FQA
By: mirek on Mon, 12 November 2007 23:34
|
|
|
Re: C++ FQA
By: mdelfede on Mon, 12 November 2007 23:33
|
|
|
Re: C++ FQA
By: exolon on Tue, 13 November 2007 17:30
|
|
|
Re: C++ FQA
By: mdelfede on Tue, 13 November 2007 18:24
|
|
|
Re: C++ FQA
By: exolon on Tue, 13 November 2007 18:58
|
|
|
Re: C++ FQA
|
|
|
Re: C++ FQA
By: mirek on Fri, 16 November 2007 11:59
|
|
|
Re: C++ FQA
By: waxblood on Fri, 16 November 2007 16:24
|
|
|
Re: C++ FQA
By: mdelfede on Fri, 16 November 2007 16:37
|
|
|
Re: C++ FQA
By: mirek on Sat, 17 November 2007 10:04
|
|
|
Re: C++ FQA
By: mirek on Sat, 10 November 2007 15:22
|
|
|
Re: C++ FQA
By: mdelfede on Sat, 10 November 2007 16:58
|
|
|
Re: C++ FQA
By: mirek on Thu, 08 November 2007 05:25
|
|
|
Re: C++ FQA
By: mirek on Wed, 07 November 2007 15:14
|
|
|
Re: C++ FQA
By: mdelfede on Wed, 07 November 2007 15:39
|
|
|
Re: C++ FQA
By: exolon on Mon, 12 November 2007 13:09
|
|
|
Re: C++ FQA
By: mr_ped on Wed, 07 November 2007 17:05
|
|
|
Re: C++ FQA
|
|
|
Re: C++ FQA
By: mr_ped on Sat, 10 November 2007 22:26
|
|
|
Re: C++ FQA
By: mirek on Sat, 10 November 2007 22:35
|
|
|
Re: C++ FQA
|
|
|
Re: C++ FQA
|
Goto Forum:
Current Time: Mon Jun 03 23:26:42 CEST 2024
Total time taken to generate the page: 0.02989 seconds
|