Spin buffers

Discussion in 'Ruby' started by John Carter, Jul 16, 2007.

  1. John Carter

    John Carter Guest

    Hmm. Just being reading the Dr. Dobbs.

    I certainly have hit the bottleneck talked about in this article...
    http://www.ddj.com/dept/architect/199902669
    when using the 'thread.rb' Queue class.

    I hacked around it by creating a Queue of Arrays, but that probably
    creates more garbage than I should.

    This "Spin Buffer" trick looks Good...
    http://www.ddj.com/dept/architect/199902669?pgno=2

    Anyone have a ruby Spin Buffer implementation lying around?

    John Carter Phone : (64)(3) 358 6639
    Tait Electronics Fax : (64)(3) 359 4632
    PO Box 1645 Christchurch Email :
    New Zealand
    John Carter, Jul 16, 2007
    #1
    1. Advertising

  2. On 16.07.2007 04:20, John Carter wrote:
    > Hmm. Just being reading the Dr. Dobbs.
    >
    > I certainly have hit the bottleneck talked about in this article...
    > http://www.ddj.com/dept/architect/199902669
    > when using the 'thread.rb' Queue class.


    What exactly makes you believe that? Can you show some code and / or
    figures that back this theory?

    > I hacked around it by creating a Queue of Arrays, but that probably
    > creates more garbage than I should.


    Difficult to say without seeing the code. Generally I'd say that Queue
    is pretty efficient already since it's implemented in C AFAIR.

    > This "Spin Buffer" trick looks Good...
    > http://www.ddj.com/dept/architect/199902669?pgno=2
    >
    > Anyone have a ruby Spin Buffer implementation lying around?


    I'd check with the RAA.

    Kind regards

    robert
    Robert Klemme, Jul 16, 2007
    #2
    1. Advertising

  3. John Carter

    ara.t.howard Guest

    On Jul 15, 2007, at 8:20 PM, John Carter wrote:

    > Anyone have a ruby Spin Buffer implementation lying around?


    no, but i'd be inclined to try writing one on top of guy's mmap ext -
    the interface is that of string so the example should map (no pun
    intended) rather well.

    cheers.

    a @ http://drawohara.com/
    --
    we can deny everything, except that we have the possibility of being
    better. simply reflect on that.
    h.h. the 14th dalai lama
    ara.t.howard, Jul 16, 2007
    #3
  4. John Carter

    MenTaLguY Guest

    --=-ZlOe4R5VzxuVmabsp2AU
    Content-Type: text/plain
    Content-Transfer-Encoding: quoted-printable

    On Mon, 2007-07-16 at 14:30 +0900, Robert Klemme wrote:
    > What exactly makes you believe that? Can you show some code and / or=20
    > figures that back this theory?


    Seconded. Measure first, then optimize.

    > > I hacked around it by creating a Queue of Arrays, but that probably
    > > creates more garbage than I should.


    That probably performs slower than Queue.

    > Difficult to say without seeing the code. Generally I'd say that Queue=20
    > is pretty efficient already since it's implemented in C AFAIR.


    Depends on the version of Ruby. It certainly is if you're using
    fastthread. If he's not using fastthread, I'd recommend giving it a
    try.

    > > This "Spin Buffer" trick looks Good...
    > > http://www.ddj.com/dept/architect/199902669?pgno=3D2
    > >=20
    > > Anyone have a ruby Spin Buffer implementation lying around?


    "Spin Buffers" are _snake oil_; they get their "speed" at the expense of
    correctness -- the implementation given in the DDJ article is not
    threadsafe. If it were rewritten to be threadsafe, it would actually be
    slower than some simpler alternatives.

    -mental

    --=-ZlOe4R5VzxuVmabsp2AU
    Content-Type: application/pgp-signature; name=signature.asc
    Content-Description: This is a digitally signed message part

    -----BEGIN PGP SIGNATURE-----
    Version: GnuPG v1.4.6 (GNU/Linux)

    iD8DBQBGnWVbSuZBmZzm14ERAuaXAKCDvGoK7xn9g6HtUKZvIfdK21GENwCeN+FG
    4b+yQIZLYbr/uaNmjYfsQgI=
    =1Ih5
    -----END PGP SIGNATURE-----

    --=-ZlOe4R5VzxuVmabsp2AU--
    MenTaLguY, Jul 18, 2007
    #4
  5. John Carter

    MenTaLguY Guest

    --=-k54+bVLBP/xUgjH/SihR
    Content-Type: text/plain
    Content-Transfer-Encoding: quoted-printable

    On Mon, 2007-07-16 at 14:46 +0900, ara.t.howard wrote:
    > no, but i'd be inclined to try writing one on top of guy's mmap ext - =20
    > the interface is that of string so the example should map (no pun =20
    > intended) rather well.


    What does mmap have to do with communication between Ruby threads?

    (and again, I'd like to emphasize that "spin buffers" are snake oil)

    -mental

    --=-k54+bVLBP/xUgjH/SihR
    Content-Type: application/pgp-signature; name=signature.asc
    Content-Description: This is a digitally signed message part

    -----BEGIN PGP SIGNATURE-----
    Version: GnuPG v1.4.6 (GNU/Linux)

    iD8DBQBGnWXWSuZBmZzm14ERAmblAKCuZDndGPOvewqbzwkVVFCGCBgKjACghyD7
    88B11PHKYrCfnBlOVtAnfUQ=
    =6FZc
    -----END PGP SIGNATURE-----

    --=-k54+bVLBP/xUgjH/SihR--
    MenTaLguY, Jul 18, 2007
    #5
  6. John Carter

    John Carter Guest

    On Wed, 18 Jul 2007, MenTaLguY wrote:

    And yes... I did, as always, measure before I optimized and my Queue
    of Array trick did speed things measurably.

    > Depends on the version of Ruby. It certainly is if you're using
    > fastthread. If he's not using fastthread, I'd recommend giving it a
    > try.


    I'm not using fastthread since it caused code that had been working
    fine for several years to curl up and die. So I disabled it.

    I'll admit I never got to the bottom of why it did.... (and no, it
    wasn't the code that used my queue of arrays trick)

    >>> This "Spin Buffer" trick looks Good...
    >>> http://www.ddj.com/dept/architect/199902669?pgno=2
    >>>
    >>> Anyone have a ruby Spin Buffer implementation lying around?


    > "Spin Buffers" are _snake oil_; they get their "speed" at the expense of
    > correctness -- the implementation given in the DDJ article is not
    > threadsafe.


    Well that was a bit of a problem with the article... it didn't
    actually include the code so I can't say one way or the other on
    that. Any pointers as to what the incorrect bit is?



    John Carter Phone : (64)(3) 358 6639
    Tait Electronics Fax : (64)(3) 359 4632
    PO Box 1645 Christchurch Email :
    New Zealand
    John Carter, Jul 18, 2007
    #6
  7. John Carter

    MenTaLguY Guest

    --=-TqNbfialWcCH6IhB/du4
    Content-Type: text/plain
    Content-Transfer-Encoding: quoted-printable

    On Wed, 2007-07-18 at 10:32 +0900, John Carter wrote:
    > And yes... I did, as always, measure before I optimized and my Queue
    > of Array trick did speed things measurably.


    Hmm, did you just mean sending batches of objects as arrays, rather than
    sending individual objects? That would make sense and it's a reasonable
    optimization, provided you're careful about not touching the array on
    the sending side once it's been added to the queue. I'd just finished
    reading the DDJ article and was imagining something more elaborate at
    first...

    > > Depends on the version of Ruby. It certainly is if you're using
    > > fastthread. If he's not using fastthread, I'd recommend giving it a
    > > try.

    >=20
    > I'm not using fastthread since it caused code that had been working
    > fine for several years to curl up and die. So I disabled it.


    It might be worth looking into why -- if it doesn't work with
    fastthread, it's unlikely to work with future versions of Ruby
    (including 1.8.6 or later) or alternate Ruby implementations like JRuby.

    Absent fastthread bugs (which do crop up occasionally, though rarely at
    this point), there are two main sources of problems:

    1. Code that tries to manipulate the internal implementation of
    thread.rb objects (Mutex, ConditionVariable, Queue, etc); not always a
    bug, but it isn't portable or future-proof.

    2. Code which has existing concurrency bugs which show up more clearly
    when the scheduling behavior changes.

    > > "Spin Buffers" are _snake oil_; they get their "speed" at the expense o=

    f
    > > correctness -- the implementation given in the DDJ article is not
    > > threadsafe.

    >=20
    > Well that was a bit of a problem with the article... it didn't
    > actually include the code so I can't say one way or the other on
    > that. Any pointers as to what the incorrect bit is?


    The code is included in the source archive on the DDJ ftp site as
    spin.txt (and spin.zip, which has his test harness):

    ftp://66.77.27.238/sourcecode/ddj/2007/0707.zip

    It's not just a one-line bug, but a systemic problem: the author assumes
    that the only reason he needs synchronization is to prevent two threads
    from modifying the same data at the same time (hence the elaborate dance
    with the buffers); in reality, however, it's also important to protect
    the code from compiler (and CPU) optimizations which will alter its
    behavior in undesirable ways if it is used in a multi-threaded context
    (e.g. it becomes possible for the reader to see the writer's addition of
    the object but see the object in an uninitalized state!). He's
    basically trying to get a performance "free lunch" by not using
    synchronization.

    Concurrency bugs are notoriously hard to find through testing, and it
    doesn't help that the author only ever tested on hardware which is
    extremely forgiving about concurrency (a single hyperthreaded x86 CPU).
    It also didn't help that all his test did was count how many objects
    were read from the queue.

    -mental

    --=-TqNbfialWcCH6IhB/du4
    Content-Type: application/pgp-signature; name=signature.asc
    Content-Description: This is a digitally signed message part

    -----BEGIN PGP SIGNATURE-----
    Version: GnuPG v1.4.6 (GNU/Linux)

    iD8DBQBGnXr3SuZBmZzm14ERAjYqAJwN3zTGPA2yKWSP8TCb6HskZb5RpQCdEQM5
    kYMM/UW66P6mSX8LOS95zYk=
    =eQEc
    -----END PGP SIGNATURE-----

    --=-TqNbfialWcCH6IhB/du4--
    MenTaLguY, Jul 18, 2007
    #7
  8. John Carter

    MenTaLguY Guest

    --=-WvSoUeP4smAk1CDL+QJ7
    Content-Type: text/plain
    Content-Transfer-Encoding: quoted-printable

    On Wed, 2007-07-18 at 10:32 +0900, John Carter wrote:
    > I'm not using fastthread since it caused code that had been working
    > fine for several years to curl up and die. So I disabled it.


    At any rate, I think your best option is something like fastthread's
    Queue. It shouldn't be too hard to change the code to work with it, and
    it's possible that you've uncovered a bug in that "working" code which
    really needs to be fixed.

    -mental


    --=-WvSoUeP4smAk1CDL+QJ7
    Content-Type: application/pgp-signature; name=signature.asc
    Content-Description: This is a digitally signed message part

    -----BEGIN PGP SIGNATURE-----
    Version: GnuPG v1.4.6 (GNU/Linux)

    iD8DBQBGnX5CSuZBmZzm14ERAiYRAKC1B9QVHdLhdidOFMIn5xjTq2m3ygCfVxzf
    IB1e5H827NKQtAwCp4owQzI=
    =nbRP
    -----END PGP SIGNATURE-----

    --=-WvSoUeP4smAk1CDL+QJ7--
    MenTaLguY, Jul 18, 2007
    #8
  9. John Carter

    MenTaLguY Guest

    --=-0qx18Y/MDA8SbomlbQdJ
    Content-Type: text/plain
    Content-Transfer-Encoding: quoted-printable

    On Wed, 2007-07-18 at 11:29 +0900, MenTaLguY wrote:
    > in reality, however, it's also important to protect
    > the code from compiler (and CPU) optimizations which will alter its
    > behavior in undesirable ways if it is used in a multi-threaded context
    > (e.g. it becomes possible for the reader to see the writer's addition of
    > the object but see the object in an uninitalized state!).


    It is worth noting that these are not issues if you're only writing for
    Ruby 1.8, which has neither an optimizing compiler nor native threads
    (where instruction ordering and cache effects become a consideration).

    So, does that mean a Spin Buffer implementation would theoretically be
    okay for Ruby 1.8? Maybe as far as those issues go. But note that the
    author himself identifies a number of issues with spin buffers when the
    readers and writers get out of sync, including poor performance and the
    reader getting "stuck" on a non-empty buffer if it hits a buffer
    boundary when no writers are writing. Those are actually inherent to
    the data structure's design.

    -mental

    --=-0qx18Y/MDA8SbomlbQdJ
    Content-Type: application/pgp-signature; name=signature.asc
    Content-Description: This is a digitally signed message part

    -----BEGIN PGP SIGNATURE-----
    Version: GnuPG v1.4.6 (GNU/Linux)

    iD8DBQBGnYD+SuZBmZzm14ERAsxWAJ92RZfVYlFqKaGEbeU327YaEs2wWgCgmLMn
    U17NBl6rgZNLvBnqdn5BdAQ=
    =aXPf
    -----END PGP SIGNATURE-----

    --=-0qx18Y/MDA8SbomlbQdJ--
    MenTaLguY, Jul 18, 2007
    #9
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Oleg
    Replies:
    4
    Views:
    6,763
    Ray Andraka
    Apr 6, 2004
  2. info
    Replies:
    1
    Views:
    523
    Richard
    Jul 21, 2003
  3. Steve Kershaw
    Replies:
    2
    Views:
    516
    Cowboy \(Gregory A. Beamer\)
    Jul 16, 2007
  4. Andrew Chalk

    Spin box control

    Andrew Chalk, Dec 4, 2005, in forum: ASP .Net Web Controls
    Replies:
    1
    Views:
    468
    Andrew Chalk
    Dec 6, 2005
  5. adicss

    3D Spin Menue

    adicss, Jun 1, 2006, in forum: Javascript
    Replies:
    1
    Views:
    125
Loading...

Share This Page