lock-free; are you using it?
Chris Thomasson
own algorithms? Do your read a academic paper and just go ahead and
implement the algorithms and use them in your production code?
Any nightmare stories that involve lock-free? Or, have you have a somewhat
positive experience?
This is just a general query...
I think I am going to have to implement something huge in order to prove the
potential benefits of lock-free tech... I want to know if anybody in this
group has been experimenting with any of the previous ideas posted in
here...
--
Chris M. Thomasson
http://appcore.home.comcast.net
Chris Thomasson
news:JYWdnbp39qf4hjbb...@comcast.com...
[...]
> I think I am going to have to implement something huge
I have tons of experience with designing high-end server software... I think
its time to bit the god damn bullet and create a fuc%ing database server! I
think Joe Seigh was thinking about doing something similar...
:^0
Joe Seigh
I just do webby stuff, mostly back end. Nothing real tricky in
the threading dept. Now I know why everyone likes GC. It makes
proper synchronization less critical. Pretty much anything will
work and you can always catch the null pointer exceptions.
STM will probably be a bust. It requires programmers to know how
to write obstruction free code. How likely do you think that will
be?
The new trend seems to be parallelization, the Intel library and
the Java 7 stuff. We'll have to see how that works out. You need
to use vectors and arrays. Storage requirements will grow so everyone
will need 64 bit machines with way more memory than you ever thought
you would need. Good for the memory mfgrs though.
--
Joe Seigh
When you get lemons, you make lemonade.
When you get hardware, you make software.
blytkerchan
(proprietary) library (for my current employer) that contains several
non-blocking synchronization tools, containers, etc. that we use in
production (after testing them thoroughly, of course).
Yes, I do read academic papers and I regularly read this newsgroup as
well.
As for nightmares: there aren't many that come to mind. There's a
memory allocator I wrote for an embedded platform that took a long
time to stabilize and debug because of the high contention it was
supposed to work with, but that doesn't really qualify as a
nightmare...
rlc
John Dallman
cri...@comcast.net (Chris Thomasson) wrote:
> If so, what has your experience been like? Are you creating and
> design your own algorithms? Do your read a academic paper and just go
> ahead and implement the algorithms and use them in your production
> code?
No. I've read some papers, and concluded that trying to apply it to a
large codebase that already has conventional locking and has to run on a
wide variety of platforms (including at least one that has no
appropriate primitives, HP's PA-RISC) is Too Hard for the present.
I am keeping the idea in reserve for future work, when we no longer have
to support PA-RISC; hitting performance problems that I can't resolve by
using normal locks in a smarter manner would move it up the priority
schedule.
--
John Dallman, j...@cix.co.uk, HTML mail is treated as probable spam.
blytkerchan
> In article <JYWdnbp39qf4hjbbnZ2dnUVZ_qain...@comcast.com>,
>
> cris...@comcast.net (Chris Thomasson) wrote:
> > If so, what has your experience been like? Are you creating and
> > design your own algorithms? Do your read a academic paper and just go
> > ahead and implement the algorithms and use them in your production
> > code?
>
> No. I've read some papers, and concluded that trying to apply it to a
> large codebase that already has conventional locking and has to run on a
> wide variety of platforms (including at least one that has no
> appropriate primitives, HP's PA-RISC) is Too Hard for the present.
>
> I am keeping the idea in reserve for future work, when we no longer have
> to support PA-RISC; hitting performance problems that I can't resolve by
> using normal locks in a smarter manner would move it up the priority
> schedule.
support, but the way I see it, if you can hide the non-blocking
aspects behind a fairly opaque interface, there is no reason not to
use whatever is best in a given situation because you can't use it
everywhere.
I.e. one of my most-used non-blocking things is a non-blocking
circular queue. The interface I provide simply promises to be thread-
safe for multiple writers and one reader, but doesn't say it is lock-
free (it is, but it isn't 100% wait-free, though it is that too except
in some very rare cases). I've hidden the implementation behind a C++
class' interface which does its job very well and is used in basically
every part of the system I work on, but if it's compiled on anything
that doesn't support the instruction set I need to be non-blocking, it
will revert to a lock-based implementation (that is still pretty
efficient, I should add).
My goal in using lock-free implementations of anything is really to
have the most efficient implementation available that is practical at
any time. As I hide everything behind some more or less opaque
interface contract of which I know I can uphold the guarantees
anywhere I support the contract in question, I can just make sure I
have the right implementation at the right time.
But like I said, I only have three platforms to work with at the
moment, and the lock-free implementations are only present on the one
we use most, so I really don't have much of a portability problem to
speak of...
rlc
Chris Thomasson
news:70Gqi.132$9I3.41@trndny06...
> Chris Thomasson wrote:
>> "Chris Thomasson" <cri...@comcast.net> wrote in message
>> news:JYWdnbp39qf4hjbb...@comcast.com...
>> [...]
>>
>>> I think I am going to have to implement something huge
>>
>>
>> I have tons of experience with designing high-end server software... I
>> think its time to bit the god damn bullet and create a fuc%ing database
>> server! I think Joe Seigh was thinking about doing something similar...
>>
>
> I just do webby stuff, mostly back end. Nothing real tricky in
> the threading dept. Now I know why everyone likes GC. It makes
> proper synchronization less critical. Pretty much anything will
> work and you can always catch the null pointer exceptions.
Yeah. I have to admit that GC's which "collect-the-world" do make things
quite easier indeed. I wonder when GC implementations are going to see that
they don't have to create something that has the ability to collect
everything in site...
> STM will probably be a bust. It requires programmers to know how
> to write obstruction free code. How likely do you think that will
> be?
perhaps, not anytime soon... ;^(
Writing obstruction-free code imho can be a pain because its falls victim to
live-lock like behavior once you apply some load on the algorithm
implementations...
> The new trend seems to be parallelization, the Intel library and
> the Java 7 stuff. We'll have to see how that works out. You need
> to use vectors and arrays.
I agree that this seems to be the way things are going... Although, Intel
better watch out for the companies that make high-end GPU's... You can
usually layout the vectors and arrays on textures and process them in the
graphics card, which is faster than using any core(s) on the host CPU...
> Storage requirements will grow so everyone
> will need 64 bit machines with way more memory than you ever thought
> you would need. Good for the memory mfgrs though.
Yup.
Chris Thomasson
news:1185640824.0...@57g2000hsv.googlegroups.com...
> On Jul 27, 12:35 pm, "Chris Thomasson" <cris...@comcast.net> wrote:
>> If so, what has your experience been like? Are you creating and design
>> your
>> own algorithms? Do your read a academic paper and just go ahead and
>> implement the algorithms and use them in your production code?
>>
>> Any nightmare stories that involve lock-free? Or, have you have a
>> somewhat
>> positive experience?
>>
>> This is just a general query...
>>
>> I think I am going to have to implement something huge in order to prove
>> the
>> potential benefits of lock-free tech... I want to know if anybody in this
>> group has been experimenting with any of the previous ideas posted in
>> here...
> I use non-blocking algorithms on a daily basis: I have written a
> (proprietary) library (for my current employer) that contains several
> non-blocking synchronization tools, containers, etc. that we use in
> production (after testing them thoroughly, of course).
What type of software are you working on?
> Yes, I do read academic papers and I regularly read this newsgroup as
> well.
>
> As for nightmares: there aren't many that come to mind.
[...]
That's good to hear. You can find some good stuff in here... For instance,
this group contains links and code-snippets that can allow one to build a
PThread library that can out perform most of the OS provided native stuff
(e.g., NPTL)...
Chris Thomasson
news:memo.2007072...@jgd.compulink.co.uk...
> In article <JYWdnbp39qf4hjbb...@comcast.com>,
> cri...@comcast.net (Chris Thomasson) wrote:
>
>> If so, what has your experience been like? Are you creating and
>> design your own algorithms? Do your read a academic paper and just go
>> ahead and implement the algorithms and use them in your production
>> code?
>
> No. I've read some papers, and concluded that trying to apply it to a
> large codebase that already has conventional locking and has to run on a
> wide variety of platforms (including at least one that has no
> appropriate primitives, HP's PA-RISC) is Too Hard for the present.
Yup. That's a pain in the neck for sure... IMHO, it can be far easier to do
a complete rewrite of an application rather than trying to augment the
existing solution with lock-free anything...
> I am keeping the idea in reserve for future work, when we no longer have
> to support PA-RISC; hitting performance problems that I can't resolve by
> using normal locks in a smarter manner would move it up the priority
> schedule.
That's sounds like a good plan.
Chris Thomasson
news:7190818.A...@tempest-sw.com...
> On Friday 27 July 2007 12:35 pm, Chris Thomasson wrote:
>
>> If so, what has your experience been like? Are you creating and design
>> your own algorithms? Do your read a academic paper and just go ahead
>> and implement the algorithms and use them in your production code?
>>
>> Any nightmare stories that involve lock-free? Or, have you have a
>> somewhat positive experience?
>
> multi-threaded. I read most of the papers, implemented some stuff
> myself, and evaluated Intel's Threading Building Blocks (TBB). My
> recommendation was to use TBB because for the support. My evaluation
> shows how lock-free performed better than traditional mutexes. I also
> showed that my code and TBB had equal performance. I recommended they
> use TBB because it comes with support.
You have to know how to leverage the power of the TBB against your existing
designs, or any new ones for that matter... If you use something from the
TBB to replace a part of an overall synchronization scheme, you mat notice
that the increase in performance will have a negative effect on another
aspect of system... More on this:
http://groups.google.com/group/comp.programming.threads/msg/9a5500d831dd2ec7
> Apparently, the project already had some lock-free code, but it never
> worked. When the author of that code left the project, all his code was
> ripped out and replaced by pthread mutexes. The code now works, and
> performance measurements suggest that the low-hanging fruit are
> elsewhere.
At least it works now! :^)
[...]
> I looked at appcode and other stuff on the net, and could not find any
> code that I would recommend for adoption in a commercial product: no
> documentation, no support, no evident license. All are show-stoppers.
The appcore lib is in pre-alpha status. However, I think I got all of the
bugs out of the experimental code... At least I have not received any
e-mails saying that anything in appcore crashed, or any bug reports on the
codebase...
Chris Thomasson
> On Jul 28, 2:03 pm, j...@cix.co.uk (John Dallman) wrote:
>> In article <JYWdnbp39qf4hjbbnZ2dnUVZ_qain...@comcast.com>,
>>
>> cris...@comcast.net (Chris Thomasson) wrote:
>> > If so, what has your experience been like? Are you creating and
>> > design your own algorithms? Do your read a academic paper and just go
>> > ahead and implement the algorithms and use them in your production
>> > code?
>>
>> No. I've read some papers, and concluded that trying to apply it to a
>> large codebase that already has conventional locking and has to run on a
>> wide variety of platforms (including at least one that has no
>> appropriate primitives, HP's PA-RISC) is Too Hard for the present.
>>
>> I am keeping the idea in reserve for future work, when we no longer have
>> to support PA-RISC; hitting performance problems that I can't resolve by
>> using normal locks in a smarter manner would move it up the priority
>> schedule.
> I guess I have the benefit of having only three hardware platforms to
> support, but the way I see it, if you can hide the non-blocking
> aspects behind a fairly opaque interface, there is no reason not to
> use whatever is best in a given situation because you can't use it
> everywhere.
You can certinaly do that. However, sometimes it can be somewhat difficult
to get the interfaces right for some lock-free algorithms...
>
> I.e. one of my most-used non-blocking things is a non-blocking
> circular queue. The interface I provide simply promises to be thread-
> safe for multiple writers and one reader, but doesn't say it is lock-
> free (it is, but it isn't 100% wait-free, though it is that too except
> in some very rare cases). I've hidden the implementation behind a C++
> class' interface which does its job very well and is used in basically
> every part of the system I work on, but if it's compiled on anything
> that doesn't support the instruction set I need to be non-blocking, it
> will revert to a lock-based implementation (that is still pretty
> efficient, I should add).
The effect of blindly swapping a lock-based implementation with a lock-free
one could have a adverse reaction wrt some other part of your
synchronization scheme... However, if your careful, you can make good use of
an abstraction of all sorts of lock-free algorithms through your own
"in-house standard" interfaces...
> My goal in using lock-free implementations of anything is really to
> have the most efficient implementation available that is practical at
> any time.
>
> As I hide everything behind some more or less opaque
> interface contract of which I know I can uphold the guarantees
> anywhere I support the contract in question, I can just make sure I
> have the right implementation at the right time.
>
> But like I said, I only have three platforms to work with at the
> moment, and the lock-free implementations are only present on the one
> we use most, so I really don't have much of a portability problem to
> speak of...
:^)
Out of curiosity, what are the platforms? Certain lock-free algorithms are
very portable, even to processors like the ARM9 which only have atomic
swap...
Joe Seigh
> On Friday 27 July 2007 12:35 pm, Chris Thomasson wrote:
>
>
>>your own algorithms? Do your read a academic paper and just go ahead
>>and implement the algorithms and use them in your production code?
>>
> I looked at appcode and other stuff on the net, and could not find any
> code that I would recommend for adoption in a commercial product: no
> documentation, no support, no evident license. All are show-stoppers.
I assume you're talking in part about the free open source stuff. There's
some good reasons for this. The main one is doing this kind of stuff
requires more resources than individual open source developers usually have
access to. After you've ported to all the platforms you have access to,
why would you do anything more than that?
There is open source stuff supported by commercial vendors but there's some
specific commercial self interest involved which may limit how broad the
support is.
And there's commerical stuff like the NOBLE library http://www.pss-ab.com/
You have to pay for it of course.
Chris Thomasson
> On Sunday 29 July 2007 10:40 am, Joe Seigh wrote:
>
>> And there's commerical stuff like the NOBLE library
>> http://www.pss-ab.com/ You have to pay for it of course.
>
http://groups.google.com/group/comp.programming.threads/browse_frm/thread/3cb6041545e55406
Use the TBB instead!
Chris Thomasson
news:12369358....@tempest-sw.com...
> On Sunday 29 July 2007 10:40 am, Joe Seigh wrote:
>
>> http://www.pss-ab.com/ You have to pay for it of course.
>
Their license model dictates that a percentage of all your product sales
must be sent to pss-ab on a periodic basis. You should ask them to e-mail
your a copy of the license model, and their API. They sent one to me.
Also, their extremely expensive. They charge $3295.00 for 3-month evaluation
license!
Dmitriy Vyukov
> > The new trend seems to be parallelization, the Intel library and
> > the Java 7 stuff. We'll have to see how that works out. You need
> > to use vectors and arrays.
>
> I agree that this seems to be the way things are going...
How parallelization can help with, for example, some network server?
Network server processes many independent requests (some requests can
be united by "sessions") and there are no "big collections" which must
be sorted/searched etc...
Yes, there are some shared collections/objects, but I think that
putting main parallelism into processing of those collections is not
the right approach... I think that parallelism must stay on request
processing level...
Dmitriy V'jukov
Dmitriy Vyukov
> If so, what has your experience been like? Are you creating and design your
> own algorithms? Do your read a academic paper and just go ahead and
> implement the algorithms and use them in your production code?
You can see this link:
http://www.thinkingparallel.com/2007/01/06/multi-threaded-challenges-in-the-game-space-a-conversation-with-tom-leonard-of-valve-fame/
Tom Leonard from Valve tells about fully-fledged lock-free engine for
their game engine.
Dmitriy V'jukov
Joe Seigh
Lock-free with back off schemes? It would help if sometimes they stated the
formal definition of lock-free just so we know they know what they're talking
about. Using CAS doesn't necessarily make something lock-free.
Joe Seigh
Now you know where the interesting challenges are. Building a better
network server with a hammer. :)
Joe Seigh
which may have implications of where these kind of libraries will come
from and who will control the api's.
Chris Thomasson
news:1185774434.5...@e16g2000pri.googlegroups.com...
Here is some thoughts this:
http://groups.google.com/group/comp.programming.threads/browse_frm/thread/6fe2dd51631afee5
Humm... Seems like they refer to a spinlock as lock-free algorithm?
Chris Thomasson
> Chris Thomasson wrote:
>> "Ray Lischner" <rl....@tempest-sw.com> wrote in message
>> news:12369358....@tempest-sw.com...
>>
>>> On Sunday 29 July 2007 10:40 am, Joe Seigh wrote:
>>>
>>>> And there's commerical stuff like the NOBLE library
>>>> http://www.pss-ab.com/ You have to pay for it of course.
>>>
>>>
>>> Thanks, I hadn't heard of that one.
>>
>>
>> Their license model dictates that a percentage of all your product sales
>> must be sent to pss-ab on a periodic basis.
>> Also, their extremely expensive.
[...]
>>
> Possibly an indication of the high cost of doing this kind of stuff
> which may have implications of where these kind of libraries will come
> from and who will control the api's.
Yeah. That makes sense... However, IMVHO, once they start demanding a % of
your product sales, well, that an instant deal breaker... I think that their
license says something about how they can audit your company to make sure
that your not keeping any product sales from them... Ouch!
;^0
Chris Thomasson
> On Jul 28, 10:25 am, "Chris Thomasson" <cris...@comcast.net> wrote:
>
>> > The new trend seems to be parallelization, the Intel library and
>> > the Java 7 stuff. We'll have to see how that works out. You need
>> > to use vectors and arrays.
>>
>> I agree that this seems to be the way things are going...
>
> How parallelization can help with, for example, some network server?
IMO, I don't think it can provide much help at all...
> Network server processes many independent requests (some requests can
> be united by "sessions") and there are no "big collections" which must
> be sorted/searched etc...
> Yes, there are some shared collections/objects, but I think that
> putting main parallelism into processing of those collections is not
> the right approach... I think that parallelism must stay on request
> processing level...
I agree.
Chris Thomasson
news:1185773997.9...@d30g2000prg.googlegroups.com...
>
>> > The new trend seems to be parallelization, the Intel library and
>> > the Java 7 stuff. We'll have to see how that works out. You need
>> > to use vectors and arrays.
>>
>> I agree that this seems to be the way things are going...
>
> I think that parallelism must stay on request
> processing level...
I wonder how Intel is going to handle the fact that a very high-end graphics
card GPU can crunch vectors and arrays faster than any of their CPU's?
:^0
blytkerchan
> "blytkerchan" <blytkerc...@gmail.com> wrote in message
read/write spinlock is one of my favorites, and I've been using it
ever since he posted it here.
rlc
blytkerchan
> "blytkerchan" <blytkerc...@gmail.com> wrote in message
parallelism involved there) a cold-fire M68K and a whole range from
the pentium family (starting at Pentium III). The C196 is really
legacy AFAIC, but we do have to put an ADT in there for some purposes,
sometimes, in which case they're usually very simple but have to be
lock-free in that an interrupt handler will have to return from using
the ADT and won't be able to "wait for the main thread" (being an
interrupt handler 'n all). At least atomicity is not a problem there.
On the pentiums, we have single-core, multi-core and SMP systems to
work with, which makes synchronization very interesting sometimes... I
still consider them only one platform, though, because the instruction
set is the same for all of them (or at least there's a common
denominator) so I can use the same code on all targets (only memory
barriers change from one pentium to another, as some don't have them)
rlc
John Dallman
cri...@comcast.net (Chris Thomasson) wrote:
> Yeah. That makes sense... However, IMVHO, once they start demanding a
> % of your product sales, well, that an instant deal breaker... I
> think that their license says something about how they can audit your
> company to make sure that your not keeping any product sales from
> them... Ouch!
There are library products that have that as a successful business
model. However, they are things that, to a first approximation, provide
all of the back-end functionality of the apps they go inside. They also
tend to have man-centuries of work inside them. They are, fairly
obviously, something that a potential customer can't even start to write
for himself.
Lock-free programming doesn't ever seem likely to provide, by itself,
such functionality, since it's a method of making applications go
faster, rather than doing anything by itself.
You can charge serious money for programming tools that are more similar
to a lock-free library, but they have to have major benefits that are
readily demonstrated and quantified. I suspect that the NOBLE guys have
tried to go commercial a bit too early, and hired an overly-aggressive
lawyer.
llothar
> I have tons of experience with designing high-end server software... I think
> its time to bit the god damn bullet and create a fuc%ing database server! I
What about writing a script language? I was thinking about this
because there is no script language available that has good
multithreading. Unfortunately i can't take the 2 years off from my
income making job to do this.
Chris Thomasson
> On Jul 28, 2:35 am, "Chris Thomasson" <cris...@comcast.net> wrote:
>> "blytkerchan" <blytkerc...@gmail.com> wrote in message
>>
>> news:1185640824.0...@57g2000hsv.googlegroups.com...
>> > As for nightmares: there aren't many that come to mind.
>>
>> [...]
>>
>> That's good to hear. You can find some good stuff in here... For
>> instance,
>> this group contains links and code-snippets that can allow one to build a
>> PThread library that can out perform most of the OS provided native stuff
>> (e.g., NPTL)...
> Oh, yeah, there are some *very* good ideas on this group. Joe Seigh's
> read/write spinlock is one of my favorites, and I've been using it
> ever since he posted it here.
Ah yes. The bakery algorithm:
http://groups.google.com/group/comp.programming.threads/msg/9f3e76e60c2cf91a
Very nice.
Markus Elfring
> because there is no script language available that has good multithreading.
Is the support by TCL good enough?
http://wiki.tcl.tk/2770
http://tcl.cvs.sourceforge.net/*checkout*/tcl/thread/doc/html/thread.html
How much will the support be growing by alternative language implementations?
http://perldoc.perl.org/threads.html#DESCRIPTION
http://logtalk.org/manuals/userman/threads.html
http://www.cs.arizona.edu/mpd/
Regards,
Markus
llothar
> > What about writing a script language? I was thinking about this
> > because there is no script language available that has good multithreading.
>
>
> How much will the support be growing by alternative language implementations?http://perldoc.perl.org/threads.html#DESCRIPTIONhttp://logtalk.org/manuals/userman/threads.htmlhttp://www.cs.arizona.edu/mpd/
This (TCL/Perl) is a shared nothing approach, so it is more or less
multiprocessing. Not that what makes this newsgroup so interesting.
There is _NO_ script language that is MT safe.
Markus Elfring
Perl and the tool command language seem to be thread-safe itself. I hope that
this property will also be achieved for more programming libraries and scripting
extensions in the near future.
Regards,
Markus
Chris Thomasson
news:1185835372.3...@j4g2000prf.googlegroups.com...
I don't have experience wrt creating an actual language. Humm... Although, I
could see how a clever use of multi-threading could help a interpreter...
Damn. Humm. I better stick to what I know!
;^0
Colin Paul Gloster
timestamped Sat, 28 Jul 2007 20:15:41 -0000,
blytkerchan <blytk...@gmail.com> posted:
|--------------------------------------------------------------------------|
|"[..] |
| |
|I.e. one of my most-used non-blocking things is a non-blocking |
|circular queue. The interface I provide simply promises to be thread- |
| |
|[..]" |
|--------------------------------------------------------------------------|
Would it be unsafe for more than one reader? If so, how and why?
Regards,
Colin Paul Gloster
Colin Paul Gloster
30 Jul 2007 05:22:47 -0700, "Chris Thomasson" <cri...@comcast.net>
posted:
|----------------------------------------------------------------------------|
|"[..] |
| |
|I wonder how Intel is going to handle the fact that a very high-end graphics|
|card GPU can crunch vectors and arrays faster than any of their CPU's? |
| |
|:^0" |
I do not know. However, before GPUs of much better processing power
than CPUs have become available, FPGAs (Field Programmable Gate
Arrays,
news:comp.arch.fpga
) had been able to outperform Intel CPUs for some kinds of problems
due to concurrency and FPGAs never displaced Intel CPUs. Perhaps
awareness of GPUs is more widespread.
Regards,
Colin Paul Gloster
blytkerchan
wrote:
> Innews:1185653741.3...@b79g2000hse.googlegroups.com
> timestamped Sat, 28 Jul 2007 20:15:41 -0000,
>> I.e. one of my most-used non-blocking things is a non-blocking
>> circular queue. The interface I provide simply promises to be thread-
>> safe for multiple writers and one reader, [..]
one reader. This is because of a race condition that would otherwise
exist on the state of the bucket (which indicates whether the bucket
can be read from or written to) and the read pointer.
To allow for more than one writer, I have a bucket state that tells
the writer whether the pointer to the bucket it just obtained is a
bucket it can still write to, and tells the reading thread whether it
can really read from the bucket. If the reading thread comes upon a
bucket it cannot read, it goes into an active wait loop until it can
read from the bucket, reads from it and puts it back in a writable
state. Though this only happens if the queue is too small for the
purposes you're using it for, it implies that if two reader threads
try to read from the same bucket, only one will be able to whereas the
other will start looping until some other thread has written to the
bucket and put it back in a readable state.
This is not a problem with multiple writers, as when a writing thread
comes upon a bucket that is not in a writable state, it will assume
some other writer preempted it and just start over. This means that,
when the queue is large enough, reading is wait-free whereas writing
is only wait-free if there is only one writer, but in all cases it is
lock-free.
We use my implementation of this lock-free circular queue in
practically every case where we have a producer/consumer problem,
which has become an extremely easy problem to solve and, because of
that, a scenario we tend to build on. At one point, we had a huge
project in production where we made our software platform basically do
things it was never designed for, and we got it all done with the same
ingredients : "a thread, a circular queue and a hammer".
rlc
blytkerchan
wrote:
> Innews:TLidnV8LjdJ1SjDb...@comcast.comtimestamped Mon,
> 30 Jul 2007 05:22:47 -0700, "Chris Thomasson" <cris...@comcast.net>
> posted:
> |----------------------------------------------------------------------------|
> |"[..] |
> | |
> |I wonder how Intel is going to handle the fact that a very high-end graphics|
> |card GPU can crunch vectors and arrays faster than any of their CPU's? |
> | |
> |:^0" |
> |----------------------------------------------------------------------------|
>
> I do not know. However, before GPUs of much better processing power
> than CPUs have become available, FPGAs (Field Programmable Gate
> Arrays,
> news:comp.arch.fpga
> ) had been able to outperform Intel CPUs for some kinds of problems
> due to concurrency and FPGAs never displaced Intel CPUs. Perhaps
> awareness of GPUs is more widespread.
tricky electronically: they don't like noise, they need to be powered
up very carefully and everybody seems to have their own idea of what
VHDL should really look (and behave) like. CPUs (and microprocessors)
are just easier to handle and to program for most...
GPUs on the other hand are far easier to program as even SIMD stays
sequential - it's just another kind of sequential...
Just my $0.02 CAN
rlc
dick...@googlemail.com
> Ray Lischner wrote:
> > On Friday 27 July 2007 12:35 pm, Chris Thomasson wrote:
>
> >>If so, what has your experience been like? Are you creating and design
> >>your own algorithms? Do your read a academic paper and just go ahead
> >>and implement the algorithms and use them in your production code?
>
> > I looked at appcode and other stuff on the net, and could not find any
> > code that I would recommend for adoption in a commercial product: no
> > documentation, no support, no evident license. All are show-stoppers.
>
> I assume you're talking in part about the free open source stuff. There's
> some good reasons for this. The main one is doing this kind of stuff
> requires more resources than individual open source developers usually have
> access to. After you've ported to all the platforms you have access to,
> why would you do anything more than that?
>
> There is open source stuff supported by commercial vendors but there's some
> specific commercial self interest involved which may limit how broad the
> support is.
>
> And there's commerical stuff like the NOBLE libraryhttp://www.pss-ab.com/
> You have to pay for it of course.
>
> Joe Seigh
>
> When you get lemons, you make lemonade.
> When you get hardware, you make software.
Hi - I wonder if I could bring your attention to a new lock free
library I've been working on for waaay too long! It's based on the
algorithms of Maged Michael (his papers seem quite well known and
available off the web). I've made the library open source and
completely free of charge, and is intended to make all this
complicated lock-free programming easy and transparent. Currently it
works on Windows, Solaris and Linux but I've only managed to test it
on Intel processors.
It's at the stage where I need to get it out into the programming
community to get people using it, and developing it further for the
various other CPU's available.
I wonder if any interested parties could download the code and have a
play about? I'd sure be grateful.
It's at www.securuslib.com and you need to go to the Downloads section
to get the s/w.
Enjoy.
Dicksters
Chris Thomasson
news:1187087540....@r34g2000hsd.googlegroups.com...
> On Jul 29, 3:40 pm, Joe Seigh <jseigh...@xemaps.com> wrote:
>> Ray Lischner wrote:
>> > On Friday 27 July 2007 12:35 pm, Chris Thomasson wrote:
>>
>> >>If so, what has your experience been like? Are you creating and design
>> >>your own algorithms? Do your read a academic paper and just go ahead
>> >>and implement the algorithms and use them in your production code?
>>
>> [...]
>> > I looked at appcode and other stuff on the net, and could not find any
>> > code that I would recommend for adoption in a commercial product: no
>> > documentation, no support, no evident license. All are show-stoppers.
>>
>> I assume you're talking in part about the free open source stuff.
>> There's
>> some good reasons for this. The main one is doing this kind of stuff
>> requires more resources than individual open source developers usually
>> have
>> access to. After you've ported to all the platforms you have access to,
>> why would you do anything more than that?
>>
>> There is open source stuff supported by commercial vendors but there's
>> some
>> specific commercial self interest involved which may limit how broad the
>> support is.
>>
>> And there's commerical stuff like the NOBLE libraryhttp://www.pss-ab.com/
>> You have to pay for it of course.
[...]
> Hi - I wonder if I could bring your attention to a new lock free
> library I've been working on for waaay too long! It's based on the
> algorithms of Maged Michael (his papers seem quite well known and
> available off the web). I've made the library open source and
> completely free of charge, and is intended to make all this
> complicated lock-free programming easy and transparent.
Yes; making effective use of lock-free programming/abstraction is easy
indeed... BTW, how are you going to handle the fact that most of Maged
Michael's works have patent applications out on them? Can you prove that
your work is not prior art?
:^/
BTW, what algorithms are you talking about? I have deeply studied IBM
patents which rendered my knowledge of Michaels work to a point where I
decided that he uses way to many _artifacts_ that are frowned upon by modern
multi-processor/core systems. IMHO, some of his algorithms seem to be
comfortable with allowing a processors coherency system to saturate itself
with interlocked RMW and memory barrier instructions. I hope you did not
follow that line of logic.
A important aspect of lock-free programming can/will boil down to the actual
number of hardware instructions an algorithm will end up having to make use
of. For instance, the lock-free queue algorithm that Michael and Scott
invented is extremely expensive because it must execute more than one memory
barrier and interlocked RMW instruction on every fast-path. Lock-free
algorithms that use more than one of those instructions will be generating
more overhead than a non-contended locking one would. Developing algorithms
that do not make use of those instructions are key. What does you library
offer within that realm of logic?
> Currently it
> works on Windows, Solaris and Linux but I've only managed to test it
> on Intel processors.
Operating systems are not really all that relevant wrt lock-free
programming. You must target the architecture.
> It's at the stage where I need to get it out into the programming
> community to get people using it, and developing it further for the
> various other CPU's available.
How many programmers do you think can do that?
;^0
[.]
Chris Thomasson
> Yes; making effective use of lock-free programming/abstraction is easy
> indeed...
I was being sarcastic. Here are just a few of the issues involved:
http://groups.google.com/group/comp.programming.threads/msg/9a5500d831dd2ec7
> BTW, how are you going to handle the fact that most of Maged Michael's
> works have patent applications out on them? Can you prove that your work
> is not prior art?
[...]
Any thoughts?
Dmitriy Vyukov
>
> > I think I am going to have to implement something huge
>
> its time to bit the god damn bullet and create a fuc%ingdatabaseserver! I
Are you talking about just some prototype database server with
restricted sql and only basic feature set? Or you are talking about
full-fledged database server with full sql and rich feature set
(materialized view, replication, fail-over etc)?
If first then, I think, nobody will use it. And even notice it. If
second then, I think, it is impossible...
I am thinking about similar thing - implement something *crazy swift*.
But I think to implement something less huge and more self-
contained...
Dmitriy V'jukov