We’re rewarding the question askers & reputations are being recalculated! Read more.
10

Things you did well Nicely formatted, easy to read. Use of typedef with structures. Things you could improve Preprocessor: Since SDL.h isn't one of your own pre-defined header files, you should be searching for it in directories pre-designated by the compiler (since that is where it should be stored). #include <SDL/SDL.h> In the C standard, §6.10....


10

Design The problem with your implementation of pop() is that it can not be implemented in an exception safe manner (for any type of T). This is why the standard implementation implements this as two different methods top() and pop(). The top() function simply returns the value while pop() does not return the value but simply removes the value from head. So ...


9

Lockless list not threadsafe I was able to break your list with a simple program: LF_List list = {0}; void *threadFunc(void *arg) { uint64_t key = (uintptr_t) arg; int i; for (i=0;i<100000;i++) { lf_list_put_if_absent(&list, key, (void *) 1); if (lf_list_remove(&list, key) == 0) { printf("ERROR\n"); ...


8

General comments The node structure is defined as a struct with private fields. This makes it a class. If it has private fields, prefer a class. The node structure is an implementation detail that is not exposed, you do not need to bother with private here. Just remove the friend declaration and remove the private and public declarations. Keep it simple ...


8

The concurrency looks bug-free to me, which is rare! Some nits on C++ idioms: It is extremely unusual to take a function pointer as a template parameter. This drastically limits the reusability of your class template. A more traditional, "STL-ish" interface would be template<class Buffer, class Produce, class Consume> class triple_buffer { ...


7

It should also be fine in earlier versions of .NET as you are not using any 4.5 specific classes or language features. The reset is fine as the assignment is atomic as you mentioned, however if you were using a long then you would want to use Interlocked.Exchange because the assignment of a 64bit number is not atomic on a 32bit operating system (as it is ...


7

A few notes, mostly unrelated to the actual lock-free nature of the code: Some of your names are a lot less meaningful than I'd like. A prime example is your template parameter S in: template<typename T, int S=5>. This should probably be renamed to something like Size instead. Although not quite as problematic, I'd say your dis and gen have pretty ...


7

One thing you should do is not use so many (if any) using namespace statements. This does make it a bit easier to write code, but it also can cause many problems with methods being confused with each other. For a detailed discussion of this, check out this question on SO. Also, you have many extra returns in your #include statements which make it look ...


7

I have taken this problem on as a little study in to lock efficiency, performance, and contention. As a result, I am posting a second answer with some additional information, and a different sort of review. Note: The full console output from my harness is here in pastebin.com First, my conclusion is that lock-free fib generator is a mistake. Reentrant ...


6

(I'm only superficially familiar with boost asio, so I'll ignore it for the rest of my post. But looking at your benchmark results, most of what I'm about to say about mutex_queue might hold as well.) Only your multi/multi case covers read/write concurrency, as in all other cases the consumers aren't started until the producers have finished. But otherwise, ...


6

I thought about a comment, but too long, several things I can think of: This does not guarantee order, i.e. an item is entered into the next free slot, and if there is a fast producer, the order the consumer sees is not guaranteed. Is this intentional? There is no atomic combined detach/attach operation, this means that for example: Thread A: Attach starts, ...


6

SingleRandom is a really bad name for your class. Single means float in C# context, so your name implies that its a Random which generates float values, which is not true. ThreadSafeRandom or SynchronizedRandom are the examples of better naming. Are you sure that using SpinLock in you case improves performance in any way? Somehow i think that a simple lock ...


6

Still not safe I haven't run the new code yet but I can already theorize at least one possible flaw. Suppose you have the following list: 4 -> 3 -> 2 -> 1 Then suppose element 2 is deleted: 4 -> 3 -> 2* -> 1 (* = marked for deletion) Now thread 1 iterates across the list and stops at element 2, and is about to delete it. ...


6

Memory ordering problem This line: if (first == m_last.load(std::memory_order_relaxed)) return false; should be: if (first == m_last.load(std::memory_order_acquire)) return false; Otherwise, on the next line you may load the wrong value out of m_buffer due to the load being reordered before the load to m_last. I ...


6

I'm not qualified to talk about memory orders, so I'll skip that part (except to note that I've never met anyone else who is, either, which is why I recommend going seq_cst all the way). I'll just pretend all your orders are seq_cst. If I understand correctly, you have one "producer" thread and N "consumer" threads. The producer pushes items onto the back ...


5

Problem with pop Your pop() function could return false when there are still elements in the list. The problem is with this check: if(!lcl_ptr.s.ptr || _head == _tail) { return false; } Here, lcl_ptr.s.ptr could be NULL if some other thread just popped that element. If that happens, you should just move on to the next element ...


5

Your code sometimes does not follow C++ Coding Conventions. Take a look at here: struct test_data { test_data( size_t e ) : expected( e ), queue(), producer_count( 0 ), consumer_count( 0 ) { } According to conventions: Consider natural language rules for spacing Readability is the goal. In general, "natural language" rules are ...


5

This is not a lock-free queue, but a locking-agnostic queue. That means, it is not safe to use on multiple threads. The reason this works in your implementation is because the push calls alter the end of the queue and the pop calls alter the beginning (so conflicts are more or less, avoided). If you tried adding elements from multiple threads at the same ...


5

BigInteger operations are slow. Each iteration through the process you are creating a new BigInteger, as well as a new FibonacciNumber instance. These instances are likely more expensive to process (and garbage collect) than the time saved through lock-free management. Still, using a three-state operation you can solve this problem without the ...


5

ABA problem I was able to break your queue (but it wasn't easy). I inserted some code to freeze one thread here in consume(): do{ // The divider's next pointer points to the next node with data. l_divider = m_divider.load(); l_snack = l_divider->m_next.load(); // divider is never null. if (nullptr == l_snack) ...


5

You have comments in the definition of RingBuffer on the value limits for some members, but there is nothing in the code that enforces that or checks to see if those limits are exceeded. Why does TryRead take its parameter by const int&? The reference is unnecessary. Just pass in the int. Why is MAX_SIZE a macro? It should be a constexpr (if your ...


5

In addition to what has already been said I would add that what happens if s is zero? You might want to throw an exception in the constructor if that happens probably because any call to count of room would fail otherwise. you can definitely improve const correctness at least in a couple of places: in explicit PCQueue(size_t s) : you can make s const. ...


5

This is sort of an extended comment on Martin York's reply. When you're doing any sort of parallel processing, I advise against re-designing pop so it requires two operations to actually remove an item from the queue, like: T val = queue.top(); queue.pop(); With sufficient care, this can work for a single-producer/single-consumer situation, but has the ...


4

This line seems really strange to me: static_assert(N!=0x80000000,"N is too large."); Technically, it is rather odd to just compare for equality with one big number where there could be numbers even bigger. Didn't you mean: static_assert(N >= 0x80000000, "N is too large."); const uint32_t MASK = 2*N-1; Since all the values in this line are known at ...


4

First, to re-iterate a point made in another answer: Making a helper class which has internal state static is a bad idea. You lose a lot of flexibility, re-usability and increase testing pain and gain nothing from it. The major problem with a static class is: You can't easily mock it for unit testing. If you want to unit test something which uses random ...


4

In order to get your code to compile, I needed to add #include <vector>, #include <cassert>, and change <class T> to <class CT> as suggested below. inline void* lock_free_forward_list_get_deadDummy() { static std::unique_ptr<void*> deadDummy_(new void* ()); return deadDummy_.get(); } This is needlessly complicated (and ...


4

Problem 1 Consider that register_idle() is equivalent to this slightly rewritten version: // this function is called by each thread when it is about to sleep void register_idle(size_t thread_id) { std::atomic_thread_fence(std::memory_order_release); uint8_t pos = idle_pos.fetch_add(1, std::memory_order_relaxed); // What happens when this ...


4

ABA problem It looks like your allocator is susceptible to the ABA problem. The allocate() function's compare and exchange is unsafe because the "next" value you are exchanging could be invalid by the time that the exchange happens. ABA Example Suppose your free list looks like this: 0 -> 1 -> 2 -> 3 Thread A enters allocate() and prepares to ...


4

Pop() has problem Consider what happens if your queue is in the following state with two jobs: m_top = 0 m_bottom = 2 The owner thread calls pop(), and loads in to local variables: top = 0 bottom = 2 Now, before the owner thread does anything else, two stealer threads call steal(), leaving the state of the queue like this: m_top = 2 m_bottom = ...


4

Serious issues with this: Memory Management. Not using RAII to lock/unlock Memory Management Don't pass pointers it does not indicate owners. Always wrap pointers in a smart pointer. Have a look at std::unique_ptr. But for types like Data there is no need to use pointers. Simply use Data as the object type (not Data*). RAII Look up the concept of RAII. ...


Only top voted, non community-wiki answers of a minimum length are eligible