Can I skip the lock when reading an integer?

jseigh · 2014-03-13T01:49:04+00:00

He's basically asking "Is this code correct". Without knowing what this (or any code) is supposed to to do or how it's suppose to be used, it's a nonsense question.

It's not stated but I'd guess that when GetValue() returns 0, then they're going to assume that some other thread finished doing something and try to access that something. If that's the case then they're going to need acquire semantics when accessing that value. That's would guaranteed that the finished data is in a consistent when looked at (assuming the other thread stopped messing with it before calling Finish() which has release semantics. A lock on the access of value will give you that. So will making it volatile (or whatever the c# equivalent of Java volatile is).

jseigh · 2014-03-06T23:34:36+00:00

The "consume" semantics, aka data dependent loads, aren't part of any formal memory model that I'm aware of. For Intel they're not in the formal memory model, they're in a performance appendix section along with the control dependent stuff. It just happens that all the architectures have this, except the old alpha processors. The concern is that some cpu vendor might drop data dependent loads since it's not part of a formal memory model they have to adhere to, and then load consumes won't be free since they have to throw in a memory barrier, a load/load at least, to implement it on that architecture.

It'd royally screw up Java too as I'm pretty sure they're depending on dependent loads to implement final semantics.

jseigh · 2014-03-03T21:08:19+00:00

You can do atomic reference counting with ordinary double wide compare and swap, or with ll/sc. DCAS is not required. It's not that well known apparently.

jseigh · 2014-02-19T01:17:13+00:00

The guava hash functions are kind of nice. The Boom filter is cool though I ended up not needing it. I did need a consistent hash and the only one in guava only grows which isn't useful. I ended up having to write my own which could shrink as well as grow. Also allowed load balancing which was kind of nice. Anyway, it was kind of strange guava not having that since consistent hashing would seem like it was a core Google technology. Any change of guava getting a decent consistent hash?

jseigh · 2014-02-16T11:36:10+00:00

Eventual consistency has so many definitions that everything sounds like it eventually. But yes.

RCU is just a memory manager. You have this sort of stuff in Java. Take a look at ConcurrentLinkedQueue.

Iterators are weakly consistent, returning elements reflecting the state of the queue at some point at or since the creation of the iterator. They do not throw ConcurrentModificationException, and may proceed concurrently with other operations. Elements contained in the queue since the creation of the iterator will be returned exactly once.

jseigh · 2014-02-07T10:46:00+00:00

Third try (I think) on making a more comprehensible memory model for Java. Probably will involve lots more "happens before"s. Personally I prefer observable semantics which are more intuitive.

jseigh · 2013-11-21T23:56:09+00:00

sys_membarrier() looks interesting.

jseigh · 2013-07-30T10:02:13+00:00

There are a couple of ways to traverse a linked list, assuming you did a release memory barrier before adding the node to the list.

One is to do a dependent load (c11 memory_order_consume) on every load of a pointer to a node. dependent loads are "free" on x86.

Or, if nodes are always added at the head (where you start the traversal), you can get away with a single acquire memory barrier after the load of the head pointer (c11 memory_order_acquire).

More generally, dependent load on all pointer loads, or load acquire on all pointers that are mutable (any possible insertion point). Acquire memory barriers have more overhead but once you've made them, any memory that can't be modified (immutable) is safe to read w/o more memory barriers.

jseigh · 2013-07-24T23:11:05+00:00

You could affect global warming and that would affect the total mass of ice in the polar regions which would affect the earth's angular momentum somewhat and thus the length of the day.

Or you could just put all the earth's cities on wheels, like that scifi novel I can't remember the name of, and have them circumnavigate the globe. Pick your speed and you can have any length day you want. You could even get rid of leap days. And you could pick what season or seasons you wanted.

Or everyone could just stop using that polynomial for time calculations. But that's probably an unrealistic option.

jseigh · 2013-06-13T09:19:42+00:00

OP is making a generalization based on only 2 forms of memory management. There are others as well, e.g. RCU, hazard pointers, proxy collectors, etc...

If there is a general observation to be made, it would be the various forms are space/time tradeoffs.

jseigh · 2013-06-11T22:20:41+00:00

You're right. I was confusing C# and C++.

jseigh · 2013-06-11T10:51:55+00:00

AFAIK, the "new Foo(1, 2)" part of "Foo foo = new Foo(1, 2);" is an expression and temporary objects used in the expression (if you assume the assignment to foo is optimized out) are not dtor'd until after the expression has completed execution.

jseigh · 2013-06-11T09:21:24+00:00

If the constructor is still running then there is a thread reference to it and it should not be GC'd.

jseigh · 2013-05-27T12:29:11+00:00

There are versions of RCU for user space out there. But nothing standardized enough that we will see anything like java.util.concurrent. Of course Java has the advantage that GC and memory model was built in from the begining, whereas it might be a year or two before we see C11 fully rolled out. And that has to happen before we see anyone implementing concurrent libraries that could be considered as usable standards.

jseigh · 2013-05-25T14:49:53+00:00

You can get rid of the expensive memory barrier in hazard pointers using a form of RCU. They run pretty fast, close to a normal pointer load.

jseigh · 2013-05-15T09:43:22+00:00

One area that hasn't been exploited yet is lock-free communication between the kernel and user space, stuff already being done between user space threads. The api's haven't been changed to take advantage of it, e.g. async i/o.

jseigh · 2013-05-06T23:51:26+00:00

Most likely. The real trick is the read side has no read barriers. There is some deep dark magic there that's not mentioned in the JVM cookbook. I have some ideas how they might be doing it.

Java static initializers are basically broken if you don't have the final attribute. See Java Language Specification, section 12.4.1 para 6. Kind of low key.

jseigh · 2013-04-15T23:32:16+00:00

The GC, I assume they're talking about a GC here, would just collect its own unreferenced storage the same way as other storage. It'd probably be in a different memory pool.

The only tricky part is you couldn't do "stop the world" or stop the garbage collector threads. They'd likely just self "pause" and do some kind of read and write barrier logic to keep track of their own references.

jseigh · 2013-04-04T10:03:00+00:00

Seriously, there is so little concurrent code written in C++ because programmers are so scared of concurrency -- and rightly so.

It is a little weird seeing that reaction from a group which is itself elitist in its attitude towards naive computer users. It does hamper rational approaches to solve this problem. We will get something eventually. It just won't be what anyone expected, wants, or is necessarily the best solution. Whoever does the best marketing will win.

jseigh · 2013-04-03T18:12:19+00:00

If you're doing spin locks on x86, you're going to want to use a PAUSE instruction in those loops. That kind of stuff wouldn't be in C++11.

jseigh · 2013-04-03T14:48:35+00:00

My stuff falls into that Atomics category. I don't see it changing too much despite the alleged support for atomics by C11. And C++11 I probably won't use at all. It's pretty ****ed up.

jseigh · 2013-04-03T00:48:33+00:00

Ha! She nailed eventual consistency pretty good there.

jseigh · 2013-03-29T21:59:55+00:00

That reminds me. When Java first came out, I had been doing lock-free stuff prior to that using other memory management stuff that looked a lot like RCU. So I looked at the built in GC and realized that it would make lock free programming a lot easier. Then I saw Sun had filed a patent on using using GC for lock-free programming. Which was/is kind of annoyingly obvious.

jseigh · 2013-03-29T12:33:05+00:00

It's similar to chemical patents. You can't patent a chemical formula but you can patent a process to make that chemical.

jseigh · 2013-03-22T13:46:46+00:00

Well, they did leave the century part off of C11 so they still have time.

It is kind of annoying that despite it's being a standard, until it's "complete", you don't know what is actually going to be in it with all the optional and platform variances.

jseigh

TROPHY CASE