gosu

How useful is a lock-free (not wait-free) approach in a real-time context? The point is that any thread contending on lock-free data is liable to starve, so the worst-case behavior is still quite bad, no? The only benefit I see is freedom from priority inversion, and that's a fixable problem anyway. Are there other properties of the system that you somehow use to get real-time guarantees?

On the other hand, if you combine interrupt-disabling with a fair lock, then your lock wait time can be bounded in every thread. This is probably only an option inside the kernel, though.

In userspace, and with more threads than CPUs, the lock-free approach probably will save you a lot of context-switching time. It'll probably also be at least as fine-grained as the most fine-grained locking scheme you can come up with, probably with less overhead.

So I'd say that the lock-free approach is an optimistic strategy, and I don't see the benefit except for performance. I say this as someone who really likes lockfree programming.

Probably the fact that it eagerly coalesces newly freed blocks where high performance allocators like tcmalloc and jemalloc use slabs of fixed-sized blocks which are never coalesced. Coalescing will load adjacent blocks into cache, and it probably implies doubly linked lists where slab allocators can get away with cache-friendlier single links or bitmaps etc. (Because you probably have to remove a block from the middle of a free list if you've just coalesced it with a newly freed block). It turns out cache footprint is key for speed and scalability in allocators, so that's a big problem.

I'm embarassed to link this twice in a row now, but at one point I played around with the perf of a couple allocators, including glibc's ptmalloc. I wound up answering exactly this question, at least for some simple use cases: http://www.andrew.cmu.edu/user/apodolsk/418/finalreport.html.

Comments in ptmalloc sources say they basically stick to the algorithm described here: http://gee.cs.oswego.edu/dl/html/malloc.html.

You don't need to have a single frontier, and IIRC no one does these days. A stack of slabs per "arena" suffices, and the extra cost is only a read from a cacheline you'll soon need anyway. It looks like jemalloc uses a tree of "runs" for that.

I don't know exactly what you're imagining, but I don't see how you can pass this off to the kernel. You need a slab which has free memory. How do you know where to find it? You could write a nasty new syscall to ask the kernel for a ZFOD page(s), and then cry because your program is slow.

Also, unless your slabs are huge and your allocator is being used to fuel some kind of pre-caching, faulting pages is going to be suboptimal. You incur at least twice as many mode switches: one for the mmap call, one for each faulting page. I've measured this, and it gets pretty expensive. I'm kind of dubious about the performance of schemes which stray from the principle of "allocate what you actually need; free it when you don't."

The bottom line is that a slab allocator should be solving a different, mostly less general problem than the kernel. It needs finer granularity and it's optimizing for common block sizes that are small enough to fit into slabs of known sizes. So it should optimize for allocating page chunks in a small subset of possible sizes (namely, the slab size(s)), while the kernel should be worried about unbounded, oddly-sized page chunks.

I toyed with scalable allocators for a course a few years back. It's a little embarassing, but if you want to see what the costs actually are: http://www.andrew.cmu.edu/user/apodolsk/418/finalreport.html

You can do lockfree slab allocators pretty easily, so the game in scalable malloc is really about avoiding inter-CPU cacheline sharing and fitting your data structures into per-CPU caches. Slabs happen to be really good for that, for non-obvious reasons.

I'm a very happy user. It's pretty well designed, and extensible in javascript. It's nice having EVERYTHING about the browser at your fingertips in fully customizable way, not just the the link-following mechanism. I use lots of vim hotkeys, just like I do in emacs.

Conkeror has sometimes struggled to keep up with xulrunner development, and there are sometimes bugs.

I suppose it was bound to happen.

By storing the struct in union with an integral type - or, if you need a value but not an address, casting to such a union. You might also think to just abuse pointer casting, but IIRC that breaks C strict aliasing assumptions and causes GCC's optimizations to do bad things to your program.

But, like you said, you still need protection of kernel data, which means that you need to execute kernel code on a stack not writeable by the user, at a greater permission level that allows ONLY the kernel code to modify kernel pages. Single-address-space or not I can't see these needs being met in a cheaper way than what we already have, presuming that kernel code/data are in never-invalidated global pages available in every address space.

Edit: Oh, I see from your other comment that you're talking about the benefits to people who don't feel this need.

Well, I'd done a small kernel for a class. Later, I wrote a lockfree malloc and realized that large lockfree programs are actually pretty managable, and that was the start. It's generally just a matter of designing around simple data structures (which are the only ones you can really do lockfree) and a repetition of some key tricks like refcounting, generation counting, and type-stable memory. Writing the data structures and primitives was tough, but otherwise you don't have to worry about locking and things come out quite neatly as a result.

Lockfree OS kernel. Give it a couple weeks.

For that price, I can buy 10 pairs of jeans on ebay, in a style that I like. Or I can go to the thrift store and get 50. I'll have wet ankles when I bike in the rain in a poncho, but whatever.

CMU's got a fairly nice one. It guides students as they build a series of compilers for increasingly large subsets of C, effectively from scratch. Course materials are public, I believe.

http://www.cs.cmu.edu/afs/cs/project/fox/mosaic/people/fp/co...

1) Math is way more than calculus. Writing proofs is the best way to train the general skills that will get you recognized as smart.

2) Stop being a coward. Always push yourself to do embarrassing, uncomfortable, or hard things, or you'll still be 16 when you're 21.

3) Gaming and computing is addictive. Don't waste precious life on it.

4) You're an idiot, and your unexamined decisions make you a bad person, though you don't intend to harm anyone. Find values to believe in, and use them to make hard or painful decisions with dignity. Foremost of those should be: treat your people well, even at your own expense.

5) Examine, accept, and embrace your feelings and your past, for better and worse.

6) Read more fiction to learn more about life.

7) You're a social animal. You'll never grow as much, or be as happy, as when you're surrounded by people.

8) Don't stop doubting yourself.

Very little of this has to do with programming or careers. But I don't regret not knowing C at 16 nearly as much as I regret all of the above. Learning to live well is so much more important.

It's true that, if you learn to enjoy CS-related work, it's thrilling and rewarding. You'll find dazzling solutions to interesting problems, and have a blast doing it. But as respectable a craft as CS work is, does your output really improve anyone's life? Probably not, and it likely even contributes to some mild social ill. And once the dopamine wears off, have the lonely hours spent solving fun puzzles in front of a screen been a good use of your time on Earth?

I'd still recommend a CS major, but I urge perspective.

That's a really good (and horrific) image. Thanks.

facepalm

What was happening is that I was trying to keep the mouse in the control strip, and it would go off the right side of the image.

Thanks a lot, Josh.

Edit: By the way, the fullscreen functionality isn't launching. But I do have a weird browser (conkeror on xulrunner 22.0).

This looks fantastic. Watching people's reactions in that example image was really interesting, and it occupied me for a good few minutes. "Why can't you do the same thing with video?" Because rewinding video is really painful, especially online video.

Criticism:

I use my thinkpad's pointer stick to move the mouse cursor. It's impossible to keep the cursor inside the "control strip" while moving it up and down and also looking away from the strip (and at the image). Too much accidental x motion is introduced.

It would be better for me if you were to enable the scroll wheel (which I can simulate on my pointer) as an alternative time control, or perhaps let me click on the control strip and then hold down mouse1 for as long as I want my y motion to control the position in time.

Why not?

Obvious ethical considerations. I'm sick of living on the death star.

It doesn't seem possible to me that any non-transparent organization with such capabilities will ever live up to some promise to "just spy on brown people". In Snowden's words: "policy protection is no protection — policy is a one-way ratchet that only loosens".

I don't think foreign spy programs are relevant to this discussion. If Pakistan jumped off a bridge, would you follow?

The main threats in the world are no longer just states

The main threats in the news are no longer just states, that's all. A few people commit criminal acts in a foreign country somtimes. Meanwhile, states have nuclear weapons and are very often in a state of war.

That same relationship does not exist [for foreign citizens].

Perhaps it should. Your reasoning was developed back when packets had their ping measured in years. One very simple reason to call Snowden a hero is that I want US tech companies to be trusted and to thus prosper, because I want to work for them.

In general, it upsets me that some narrative has taken hold where, because "non-US persons" are on the internet, it's OK for a non-transparent agency to listen to everything on the internet, and high treason for someone to attempt to save me from it. Living in China for a couple days and talking to the news isn't "going to the enemy", as you'd so like me to see it.

Snowden is a story too. As someone who considers him a hero, and one of the rare few who I can relate to, I'd like to know more about him views so that I can learn from him. That's not irrational, unless you think biographies are a waste.

In this regard, I wonder if any potential underhanded focus on character rather than message in the media might have the ironic effect of empowering more young people. "You can do good and be brave even if you play WoW".

Not if you compile via LLVM/clang.

The same party is already in control of the world's PCs and laptops - things everyone with an XBone will already use for many of their favorite illegal activities. What new danger does this introduce?

I also expect that if video/audio are being saved or else transmitted to Microsoft/NSA or else being dynamically analyzed using the latest wank-detection algorithms, then someone will detect this by the resource usage.

  Surely you must mean C**, which is the type of a thing 
  which you can dereference twice to get C. Otherwise, 
  you're dereferencing C twice, which gets you machine 
  instructions, I guess.

What if, like the second best selling book ever, it takes almost a decade for the book to begin selling well? If books can cease to produce money just as their popularity begins to crest, then I imagine publishers will be less eager to publish things that aren't likely to be immediate hits. I have the impression that many of the books which our culture treasures weren't immediate hits.

It's true that some governments have killed their own citizens unjustly and en masse. I don't think that my own government poses such a threat to me. If you're a US citizen who feels like their government was designed to efficiently kill its citizens, and if you think that you can prevent that, then we probably can't have a constructive discussion.

I don't know if people just want to start a interesting conversation, or if they feel like disparaging government somehow refutes my point. I hope it's the former, because it doesn't. If you understand why I don't want people to have access to tools designed to kill people like me, but consider government to be an existential threat, it should still be pretty obvious that the list of priorities is something like 1. handguns, 2. rifles, ..., N. governments.

None of those were designed to efficiently kill people like me. The OP's point is that I should be worrying more about handguns, and he's right - but that doesn't mean I can't worry about other things designed to pose a threat to my person too.

AK-47s scare me about as much as any other gun.

It's "good" that rifles are used to kill fewer people than other weapons, and we should choose our battles accordingly.

That doesn't change the fact that I want to make it as hard as possible for crazy people or people on a power trip to be able to fashion machines designed to efficiently kill people like me. That seems like a simple principle.

Maybe the best way to achieve that here is to let these things stay in obscurity. Maybe not.

I wouldn't call that canonical. You can take a further step, as in the Linux version that someone posted below:

http://kernelnewbies.org/FAQ/LinkedLists

Very cool. What kind of lockfree linked lists? Did you work from one of the papers on the subject?

(Searching "rust lockfree" reveals a feature request for a lockfree malloc. I happen to have one of those, but the reality is that synchronization will probably not be your bottleneck.)

The correct way to do linked lists is to store the list traversal fields next to the data. In C, this would mean storing next/prev pointers inside of the structs which will be placed on lists.

In light of this, the things in the OP are often non-issues because you'll need the data in cache immediately after the list operation anyway (or during the traversal, for O(n) operations like list_find). In fact, vectors of pointers are worse for the hardware because you'll need to load in more cache lines than with lists, in order to traverse the array.

Lists aren't clearly the better option when the data will need to live exactly as long as the data exists in the container. In this case, you can store the data itself in a vector's backing array (and so the data will be invalid as soon as it's removed from the vector).

I think that such a developer would be equally as likely to forget to free() memory or overflow a buffer. I assume that the reasoning is that people who don't know C well enough or are too forgetful shouldn't be working on the Plan9 codebase anyway, so why optimize for such a bad case when there are definite costs to doing so (as I mentioned before)?

OS code has to do a lot of validating input and braceful style causes functions to be visually dominated by boring validation code. It's also surprisingly nice to have a visual distinction between boring conditions like if(!found) return; and the more interesting branches that require the braces.

Not sure I follow you on the one; two; example. Why would you have two statements per line in the first place? (You do realize that the "two;" isn't in the if block, right?)