cristom

cristom cristom

Niner since 2006

Comments

  • Programming in the Age of Concurrency: Software ​Transaction​al Memory

    DAMN! This fourm software mess my post again!!!

    ArGH! Let be try one more time!

    Here they are the introductory papers I used for my vZOOM coolthreads project...

     

    http://appcore.home.comcast.net/vzoom/

     

    http://appcore.home.comcast.net/vzoom/round-1.pdf

     

    http://appcore.home.comcast.net/vzoom/round-2.pdf

     

    http://appcore.home.comcast.net/vzdoc/atomic/static-init/

     

     

    This is a major alternative to STM. It outperforms it by orders of magnitude. The video should have mentioned other ways of doing things.

     

    Any thoughts?

     

     

    -- P.S. this is in regard to the SUN CoolThreads contest:

     

    https://coolthreads.dev.java.net/

     

     

  • Programming in the Age of Concurrency: Software ​Transaction​al Memory

    Here they are the introductory papers I used for my vZOOM coolthreads project...

     

    http://appcore.home.comcast.net/vzoom/

     

    http://appcore.home.comcast.net/vzoom/round-1.pdf

     

    http://appcore.home.comcast.net/vzoom/round-2.pdf

     

    http://appcore.home.comcast.net/vzdoc/atomic/static-init/

     

     

    This is a major alternative to STM. It outperforms it by orders of magnitude. The video should have mentioned other ways of doing things.

     

    Any thoughts?

     

     

    -- P.S. this is in regard to the SUN CoolThreads contest:

     

    https://coolthreads.dev.java.net/

     

  • Programming in the Age of Concurrency: Software ​Transaction​al Memory

    I almost forgot that the video mentions that they have to use Garbage Collector. I have STM that does not depend on a GC at all. Funny… I wonder why Simon and Tim depend on a GC? Its clearly not needed… A lightweight PDR scheme can implement STM…

  • Programming in the Age of Concurrency: Software ​Transaction​al Memory

    Can you use STM to efficently solve this problem:

    http://appcore.home.comcast.net/vzdoc/atomic/static-init/

    Any thoughts?
  • Programming in the Age of Concurrency: Software ​Transaction​al Memory

    For the record, I did not call you stupid. I want to know how you would address the Cell SPU with STM, that all...

    :^)
  • Programming in the Age of Concurrency: Software ​Transaction​al Memory

    “As for me not wanting to learn anything new… Well you wrong. I implemented STM. I know all of the issues. I have to make sure that I let everybody know what’s up, and let them get mislead by the marketing for STM."

     

    ACK...

     

    I meant:

     

    As for me not wanting to learn anything new… Well you wrong. I actually implemented several versions of STM; I know all of the issues. I have to make sure that I let everybody know what’s up, and NOT let them get mislead by the marketing for STM.

  • Programming in the Age of Concurrency: Software ​Transaction​al Memory

    "Again, if you validate x and y before computing the if statement in A, it can't go wrong. This is not an unavoidable problem."

     

    Okay, well that makes STM doubly expensive. You have to see if you can commit, before you try to commit? What if your validation contains thousands of read transactions? How to address very large shared linked data-structures in STM without livelock and explicit contention management?

  • Programming in the Age of Concurrency: Software ​Transaction​al Memory

    Why would you use STM in a game engine? And how would use use STM on the Cell? Perhaps I, or somebody else at comp.programming.theads can help you get a MUCH better design for any engine you may be working on.

    

     

     

    "You do know that the founder and technical director (Tim Sweeney)of Epic games (recently released Gears of War for the XBox 360) is a heavy advocate for purely functional programming and STM for games, right? If not, check out "The Next Mainstream Programing Language, A Game Developer's Perspective". But I'm sure you know more than both him and me."

     

    Yeah. Well, if Tim says so... I happen to completely disagree with him. BTW... Sadly, a lot of game programmers are not talented multi-threaded programmers:

     

    http://groups.google.com/group/comp.programming.threads/msg/2c477272953fc5e0

     

    http://groups.google.com/group/comp.programming.threads/browse_frm/thread/6fe2dd51631afee5

     

    http://groups.google.com/group/comp.arch/search?hl=en&group=comp.arch&q=games+multi-core&qt_g=1

     

     

    That’s the sad truth. STM is not going to help them learn how to leverage lock-free programming against their very high-end game engines synchronization needs. I bet Tim doesn’t let his programmers use any Assembly Language either? I doubt it. I also doubt that he would choose a STM based engine, over a lock-free engine that outperforms it by an order of magnitude. He would have to be crazy to do something like that.

     

    IMHO, game programming is all about squeezing all of the horsepower you can out of the architecture. STM prevents this because it will be flooding the cache coherency system with boat loads of unneeded traffic. Humm… Assembly language and game engines… Do they go together? Yes. Big time. Its going to be interesting to see how the gaming industry programs the Cell with STM… Wow. Its basically impossible. How to address the SPU with STM?

     

     

    As for me not wanting to learn anything new… Well you wrong. I implemented STM. I know all of the issues. I have to make sure that I let everybody know what’s up, and let them get mislead by the marketing for STM.

  • Programming in the Age of Concurrency: Software ​Transaction​al Memory

    “E.g. let's say you have a game world, and 10000 game objects that interact with it in complex and data dependent ways (i.e. there is no way to partition the world into lockable regions). Each of these objects interact with about half a dozen of the other objects, and they do so concurrently, and the interactions must be atomic. How do you solve that with lock free data structures? The game world consists of multiple different data structures nested in complex ways (oct-trees, portal cell graphs, BSP trees, etc.). How do you solve it with locks? You really don't, unless you stick a big lock on the entire world, or use some global locking order or something equally detrimental to composability and productivity. STM in this case "Just Works".”

     

     

    If you don’t know how to write a high-end multi-threaded game engine without using STM, that’s your problem. Game engines HEAVILY benefit from assembly language and other assorted low-level tricks and techniques. Low-overhead lock-free algorithms are a must. STM in a game engine? No way. I want my game to be very fast. STM would prevent the game engine from realizing the full potential of today’s high-and architectures…

     

    BTW, how would STM work on the Cell Processor? I don’t think it’s even possible for STM to even being to make use of the Cells SPU’s. Ha…. You want to program games? Do you know assembly language inside in out? Do you know how to use DMA with the Cells AltiVec SPU to shunt from shared memory to local SPU memory?  Do you know the PPC instruction set? Do you know distributed/network programming paradigm for the Cell? What about the XBox 360? Why bog down its PowerPC with all of the coherency traffic generated from the crappy TM?

     

    You want to get into game engines? I suggest posting something overing comp.programming.threads and/or comp.arch. BTW, have you ever programmer the IBM Cell Processor or have you done any lock-free synchronization algorithms that use the PPC instruction set? Do you know the AltiVec instruction set? I have experience with all of these. I would not want you on the design team if alls you have to say to synchronization issues in the game engine is STM… No way no how!

     

    How skilled are you wrt high-end game engine synchronization issues? They are basically the same issues that exist in the fast-pathed part of a database server… Anyway, please follow-ups in comp.programming.threads and/or comp.arch. This forum seems to get too crowed...

     

    Humm…

  • Programming in the Age of Concurrency: Software ​Transaction​al Memory

    One problem with implementing software transactional memory is that it's possible for a transaction to read inconsistent state (that is, to read a mixture of old and new values written by another transaction). Such a transaction is doomed to abort if it ever tries to commit, but it's possible for inconsistent state to cause a transaction to trigger a fatal exceptional condition such as a segmentation fault or even enter an endless loop, as in the following contrived example from Figure 4 of "Language Support for Lightweight Transactions":

    atomic {
        if (x != y) 
            while (true) { }
    }
    

    Transaction A

    atomic {
        x++;
        y++;
    }
    

    Transaction B

    Provided x=y initially, neither transaction above alters this invariant, but it's possible transaction A will read x after transaction B updates it but read y before transaction B updates it, causing it to enter an infinite loop. The usual strategy for dealing with this is to intercept any fatal exceptions and periodically check if each transaction is valid; if not, it can be aborted immediately, since it's doomed to fail in any case.

  • Programming in the Age of Concurrency: Software ​Transaction​al Memory

    One other MAJOR *point about TM... STM or HTM, my implmentation or not, both "suffer" from a not so well known phenomena:

    Inconsistent data can, and will, be accessed in a transactional atomic block! A users algorithm for a transactional based system is based solely inside of an atomic block, e.g.,


    atomic { // start transactional atomic block 
     
    users_algorithm{
       // Access transactional data-structures
     }

    } // try to commit transactional atomic block


    This means that the users algorithm can actually "operate" on inconsistent data... No kidding, not at all... therefore, a users algorithm behavior is basically undefined, whether the programmer likes it or not... Think about it for a minute... If your algorithm is fed with "no-so coherent" data, then your algorithm will be subject to undefined behavior by default...

    Wow... The implementations that I have seen have to actually catch any and all fatal exceptions that can, and WILL, arise when a user algorithm is subjected to inconsistent data... Sometimes your algorithm crashes right off the bat and gets intercepted by the STM where the transaction will be aborted, and retried... Sometimes your algorithm will be stuck in an infinite loop (most common problem, IMHO) , inside the atomic block... STM has to watch out for this kind of stuff... IMHO, this is a MAJOR drawback and a down right dangerous aspect of transactional memory... This behavior is inherent in basically any TM implementation; hardware or software...

    Need to think some more on this troubling subject... Now you know just some of the reasons why I don't like TM...

    Yikes!

    :O

    * I can't believe I forgot to mention this; totally slipped my mind. Right when I remembered this I went over to Wikipedia to see if anybody bring this fact up; somebody did... IMO, its vital that anybody who thinks about using TM completely understands this particular caveat!

  • Programming in the Age of Concurrency: Software ​Transaction​al Memory

    "Actually I'm really not. I've posted twice why I don't think this makes sense in an imperative language."

     

    I think we have to agree to disagree on this. I have no problems with using C for creating high-end multi-threaded applications.


     

    "I would recommend you post it and point it in the direction of Simpon Peyton Jones and Tim Harris though. If your implementation really is as good as you say, and it does what the Haskell one does, I'm sure they will be willing to do it your way instead."

     

    Its definitely as good as I say it is, however, it doesn’t have some of the features that Haskell has. You should think of my STM as a “lean-and-mean” minimalist version. I was trying to go for extreme speed in the STM implementation itself, some of the stuff that Haskell uses makes this impossible.

     

    ;^(…

     

     

    Anyway… I will think this over. To patent, or not to patent. I wonder how popular a fairly speedy C/C++ STM alternative to Haskell would actually be. I personally would not even want to use my STM in any of my application infrastructures’. But if most of the programmers go for STM, I could do well by providing a top-notch minimalist alternative in C/C++.

     

     

    Humm..

View All