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.
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.
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.
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.
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.
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.
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.
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".
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.
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.