Jump to content
  • Advertisement
Sign in to follow this  
BradDaBug

Unity Critique my lockless queue, Part II

This topic is 3091 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

This is kind of a continuation of this thread. I found this GDC 2008 presentation from Microsoft where the presenter defines "channels" as a way to do IPC. He specifies some rules the channels must follow: * Writes are atomic and non-blocking * Reads block if queue empty * Supports multiple readers: each message is read once and only once Judging from his code examples in other places in the presentation it looks like channels are also expected to be able to support multiple writers in different threads too. He mentions using XLockFreeQueue as a way to implement channels (I don't have an XDK, so I don't know any of the guarantees the XLockFreeQueue makes or how it works), or that a deque and a semaphore could also work on Windows. Well, I couldn't figure out how to make a deque threadsafe without using locks and whatnot, so I made this... It's a LIFO stack implemented with a singly-linked list! Okay, it's not really a queue, but like I said, I couldn't figure out how to make a lock-free queue that followed the rules of the "channel," so I went back to something simpler and made this.
template<typename T>
class MessageStack
{
    struct Node
    {
        volatile Node* Next;
        T Data;
    };

    volatile Node* m_head;
    SDL_sem* m_semaphore;


public:
    MessageStack()
    {
        m_semaphore = SDL_CreateSemaphore(0);
        m_head = NULL;
    }

    ~MessageStack()
    {
        SDL_DestroySemaphore(m_semaphore);

        while(m_head != NULL)
        {
            volatile Node* n = m_head;
            m_head = m_head->Next;

            _aligned_free((void*)n);
        }
    }

    void AddMessage(T message)
    {
        Node* n = (Node*)_aligned_malloc(sizeof(Node), sizeof(void*));
        n->Data = message;

        while(true)
        {
            n->Next = m_head;
            
            if (InterlockedCompareExchangePointer((volatile PVOID*)&m_head, n, (void*)n->Next) == n->Next)
                break;
        }
        
        // let any waiting readers know there's an available node
        SDL_SemPost(m_semaphore);
    }

    // blocks until a message is available, and then removes it from the list
    T RemoveMessage()
    {
        // block the reader until we have something available
        SDL_SemWait(m_semaphore);

        volatile Node* n = NULL;
        while(true)
        {
            n = m_head;

            if (InterlockedCompareExchangePointer((volatile PVOID*)&m_head, (void*)m_head->Next, (void*)n) == n)
                break;
        }

        T t = n->Data;
        _aligned_free((void*)n);

        return t;
    }

    // attempts to get the next message, but won't block.
    // returns true if a message was received, false otherwise
    bool TryRemoveMessage(T* message)
    {
        if (SDL_SemTryWait(m_semaphore) == 0)
        {
            volatile Node* n = NULL;
            while(true)
            {
                n = m_head;

                if (InterlockedCompareExchangePointer((volatile PVOID*)&m_head, (void*)m_head->Next, (void*)n) == n)
                    break;
            }

            *message = n->Data;
            _aligned_free((void*)n);

            return true;
        }

        return false;
    }
};
It uses a semaphore (I happened to use SDL instead of Win32, but the basic semaphore operations should be obvious) to make the reader block if there is nothing in the list to read. I think it meets all the requirements of a "channel." So how does it look?

Share this post


Link to post
Share on other sites
Advertisement
Which compiler(s) are you targeting? volatile means different things to different compilers.

For this reason, I'm even tempted to make the somewhat more blankety statement that using volatile qualification should be viewed as a bug.

Share this post


Link to post
Share on other sites
Right now I'm just focused on Visual C++ 2005 and 2008.

InterlockedCompareExchangePointer() requires volatile pointers for the first parameter. Why wouldn't I want to use volatile?

Share this post


Link to post
Share on other sites
Quote:
Original post by swiftcoder
Quote:
Original post by BradDaBug
Why wouldn't I want to use volatile?
Required reading on the topic.

In your case, volatile is likely doing exactly what you intend it to, but this usage isn't portable.


Agreed.

OP: If you're putting together lock-free code, it's super important that you know what volatile really means, or rather, know what it really doesn't mean.

For this reason, I would recommend that you add pre-processor checks to ensure that the code is only compiled with Visual C++ 2005 or later, if you intend to distribute code in source form.

It will fall apart with a number of other compilers. Even better, re-write the code such that volatile isn't needed (by inserting the assumed fences and so on explicitly).

Share this post


Link to post
Share on other sites
volatile is required for variables to be used with the Interlocked* functions only to ensure the compiler doesn't re-order (or otherwise optimise) reads and writes to the variable.
Any call to an Interlocked* function will create the required memory fence to ensure that none of these optimisations occur at run-time.

AFAIK, this usage of volatile should be portable across any compiler.

BradDaBug's code doesn't seem (I'd have to look closer to make sure!) to rely on the non-standard behaviour of volatile adding memory-fences -- the interlocked API does that for him (and this API requires your variable to be marked volatile, otherwise the fence would be useless if the compiler is going to reorder things anyway!).

Share this post


Link to post
Share on other sites
Quote:
Original post by Hodgman
volatile is required for variables to be used with the Interlocked* functions only to ensure the compiler doesn't re-order (or otherwise optimise) reads and writes to the variable.
Any call to an Interlocked* function will create the required memory fence to ensure that none of these optimisations occur at run-time.

AFAIK, this usage of volatile should be portable across any compiler.

BradDaBug's code doesn't seem (I'd have to look closer to make sure!) to rely on the non-standard behaviour of volatile adding memory-fences -- the interlocked API does that for him (and this API requires your variable to be marked volatile, otherwise the fence would be useless if the compiler is going to reorder things anyway!).



You're contradicting yourself. First you say that the usage of volatile to ensure that the compiler doesn't re-order access should be portable, then you say it's nonstandard behavior of volatile adding memory fences. That's exactly what memory fences are for, making sure operations aren't re-ordered.

FWIW, it's Microsoft specific behavior, and as far as the C++ standard goes, it says nothing about re-ordering or anything of the sort. volatile is almost completely useless if you're only interested in it's standard defined behavior.

Share this post


Link to post
Share on other sites
Bob pendleton has added some preliminary support for more low level multithreading primitives for SDL 1.3, analogous to InterlockedCompareExchange etc You might find it interesting.

Share this post


Link to post
Share on other sites
Quote:
Original post by cache_hit
Quote:
Original post by Hodgman
volatile is required for variables to be used with the Interlocked* functions only to ensure the compiler doesn't re-order (or otherwise optimise) reads and writes to the variable.
Any call to an Interlocked* function will create the required memory fence to ensure that none of these optimisations occur at run-time.

AFAIK, this usage of volatile should be portable across any compiler.

BradDaBug's code doesn't seem (I'd have to look closer to make sure!) to rely on the non-standard behaviour of volatile adding memory-fences -- the interlocked API does that for him (and this API requires your variable to be marked volatile, otherwise the fence would be useless if the compiler is going to reorder things anyway!).
You're contradicting yourself. First you say that the usage of volatile to ensure that the compiler doesn't re-order access should be portable, then you say it's nonstandard behavior of volatile adding memory fences. That's exactly what memory fences are for, making sure operations aren't re-ordered.

FWIW, it's Microsoft specific behavior, and as far as the C++ standard goes, it says nothing about re-ordering or anything of the sort. volatile is almost completely useless if you're only interested in it's standard defined behavior.
Nope, Hodgman is correct. The key here is that the 'volatile' keyword isn't doing much of anything - it is merely a requirement of the Interlocked* functions. The Interlocked* functions themselves handle the memory fences, so the code as it stands is perfectly valid.

Equally, the reason it isn't portable has nothing to do with the use of volatile - instead it is the fact that the Interlocked* functions are Windows-specific.

Share this post


Link to post
Share on other sites
Quote:
Original post by swiftcoder
Nope, Hodgman is correct. The key here is that the 'volatile' keyword isn't doing much of anything - it is merely a requirement of the Interlocked* functions. The Interlocked* functions themselves handle the memory fences, so the code as it stands is perfectly valid.

Equally, the reason it isn't portable has nothing to do with the use of volatile - instead it is the fact that the Interlocked* functions are Windows-specific.


Maybe I'm misreading his sentence, but this is what I see.

Quote:

volatile is required for variables to be used with the Interlocked* functions only to ensure the compiler doesn't re-order (or otherwise optimise) reads and writes to the variable.

...

AFAIK, this usage of volatile should be portable across any compiler.


According to the standard, volatile has nothing to do with whether or not a compiler re-orders reads or writes to a variable. It's required because a) the function signature demands it, and b) it just so happens that msvc does use memory fences on volatile accesses. But I still dont' see anything "portable" about this usage of volatile at all.

Am I missing something?

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
  • Advertisement
  • Popular Tags

  • Popular Now

  • Advertisement
  • Similar Content

    • By Hive Entertainment
      I have already chosen my favorite from the concept artist which one do you like better 1 2 or 3?
       
      Also still looking for a writer and a 3d artist message if you are interested!

    • By Armaan Gupta
      Hey There,
      I am a developer and Im working on a blockchain based infinite runner type game. Right now, I am working on releasing the beta version with a couple other game developers, but would love to expand the team and have other talented and bright people contributing. The game portion of the project isnt very complicated, and wouldnt require anyone to pull thier hair out for it.
      If you are interested in joining a project, interested in the idea, or would like some more information, please don't hesitate to ask either by commenting, discord (username: Guppy#7625), or by email (armaangupta01@gmail.com).
      Thank you!
    • By Joydeep Mani
      I am trying to build a particle system for unity based on "Destiny particle architecture " released in Siggraph.
      I encounter a problem in trying to understand how they iterated this:

      Converted to spline function and the result is

      i wanted to know how did they converted the function in the editor to represent the graph ??
       
    • By Xerath Dragons
      This is my first experiment use for create my original character little cute dragon chibi use zbrush and blender and use unity3d assest free for enviroment scene you have feedback?
       


    • By Aryndon
      Project Redemption is an semi-fantasy RPG with a linear story and an elaborate combat system.
      We are building in Unity and are currently looking animators and artists.
      What we are looking for
      -Someone who is okay with split revenue/profits when finished
      -Collaborate with others in the team. Do you have an idea/thought on what should be included? Tell us!
      -Someone who wants to work with people that are passionate about this project
      If you are interested. Please message me and I will get back to you as soon as possible! Or add me on Discord AJ#6664
    • By Aggrojag
      Hello!
      I'm working on a game that is a narrative driven dark comedy with some small aspects of platforming and puzzle solving. The project is rather small as well. It touches on topics such as suicide, mental illness, family, corruption, free-will, and redemption.
      This project is exercise in polish, this means some experimentation will be needed along with some reworking of assets as they're provided.
      This will be a revshare model.
      First, I'm looking for a 2D sprite artist, not pixelated, that can compliment the style of the attached images, and be similar to the temporary character.
      We are looking to bring on a SFX designer at this time. Full list of required SFX will be available upon request, as well as a build with all elements related to sound implemented in some form (many SFXs pulled from the web for now). Will likely require some field recording, and some pretty strange SFX for when things get weird. I imagine a good portion of these will be quite fun to create.
      Lastly, I'm looking for a male voice actor, English should be your primary language. There will be at minimum two characters that will need to be brought to life through vocals. The first voice is similar to Marvin from Hitchhiker's Guide to the Galaxy. A reference for the second voice would be a mix of Ren (Ren & Stimpy), and Android 21 (DragonBallFighterZ). Due to formatting, I'm not including YouTube links in the post, sorry.
       
      WIP Scene with our custom shaders attached (platforms are lazily placed, as this was an asset test):

      A scene with dynamic lighting and temp character:

       
      Unshaded asset:

      If you made it to the bottom, thank you, and I look forward to hearing from you.
    • By SickTwistGames
      Ok, firstly, Hi.
       
      This is my first post on this forum. I am an Indie Dev making my first game so bear with me when I say dumb stuff, I'm on a huge learning curve.
       
      My first question is about inventory systems for unity. I am trying to make a survival type game with crafting. I have purchased Inventory manager pro by devdog from the unity asset store and it seems like a pretty powerful assett but for an intermediate coder its a little tough to use.  I'm beginning to wonder if it was the right purchase.
      So my question is.... does anyone have any experience of inventory plugins / systems for unity and can anyone reccomend a system to me?
      It needs to have the following: Loot system, crafting system, character sheet, blueprint system,  character stats system. Ideally with as little coding as possible.
       
      Thanks
    • By ethancodes
      I've got a bug with my brick breaker style game. The bricks move down one line at a time ever 1.5 seconds. What appears to be happening is occasionally the ball will be just about to hit the brick when the brick moves down a line, and now the ball is behind it. I'm not sure how to fix this. I have two ideas but I'm not sure of implementation. 1 solution would be to check where they were and where they are going to be before rendering the frame. Then if they crossed paths, then register the brick as hit. Solution 2 would be change how the bricks move. I could maybe slide them down line by line, instead of a jump down. I'm not sure of this will fix the issue or not. Any ideas?
    • By Pixeye
      I wrote an extension for unity inspector that allows to group/fold variables. 
      Available on github  , cheers!

       
    • By rakshit Rao
      I'M interested in programming tools (For animation, UI, etc). Can anyone suggest me the resources where I can start learning or which technologies I need achive it.
       
      Thanks,
      Rakshit
  • Forum Statistics

    • Total Topics
      631067
    • Total Posts
      2997737
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!