luckydude · HackerTrans

8 tahun yang laludiscuss

That was hard to read, your love for the man is so clear.

Good luck in your goal to accomplish what you can.

9 tahun yang laludiscuss

I get that you can work around the problems, you don't seem to get that from a math point of view, rebase forces either

a) a centralized model

or

b) you have to throw away any work based on the dag before the rebase

or)

c) you have the history in the graph twice (which causes no end of problems).

(a) is the math way, (b) and (c) are ad-hoc hacks. You are well into the ad-hoc hacks, you've found a way to make it work but it includes "don't do that" warnings to users. My experience is that you don't want to have work flows that include "don't do that". Users will do that.

luckydude

9 tahun yang laludiscuss

So the current BK doesn't really have branches, it has the model that if you want to branch you clone, each clone is a branch.

Which begs the question "how do you do dev vs stable branches?" And the answer is that we have a central clone called "dev" and a central clone called "stable". In our case we have work:/home/bk/stable and work:/home/bk/dev. User repos are in work:/home/bk/$USER/dev-feature1 and work:/home/bk/$USER/stable-bugfix123.

We run a bkd in work:/home so our urls are

    bk://work/dev
    bk://work/$USER/dev-feature1

BK has a concept of a level - you can't push from a higher level to a lower level. So stable would be level 1, dev would be level 2. Levels propogate on clone so when you do

    bk clone bk://work/dev dev-feature2

and then try and do

    bk push bk://work/stable

it will tell you that you can't push to a lower level. This prevents backflow of all the new feature work into your stable tree.

The model works well until you have huge (like 10GB and bigger) repos. At that point you really want branches because you don't want to clone 10GB to do a bugfix.

Though we addressed that problem, to some extent, by having nested collections (think submodules that actually support all workflows, unlike git, they are submodules that work). So you can clone the subset you need to do your bugfix.

But yeah, there are cases where "a branch is a clone" just doesn't scale, no question. But where it does work it's a super simple and pleasant model

luckydude

9 tahun yang laludiscuss

Nope, you want what I called the event stack. It lets you have your cake and eat it too.

The event stack is a record of every tip that was ever present in this repo other than unpushed commits.

You were at cset 1234, you pull in 25 csets, the event stack has two events, 1 which points to 1234 and 2 which points at the tip after the pull.

You commit "wacked the crap out of it", then commit "fixed typo", then commit "added test", then commit $whatever. The event stack is

1 2 . which points at your current tip but is floating

Now you push. Your event stack is 1, 2, 3 and 3 points at the tip as of your push.

What about clone? You get your parent's event stack but other than that they are per repo.

The event stack is the linear history you want, it is the view that everyone wants. It's "what are the list of tips I care about in this repo?". Have a push that broke your tree but you don't know what the previous tip was because the push pushed 2500 commits? No problem. The event stack is a stack and there is a "pop" command that pops off the last change to the event stack. So you would just do "git pop" and see if that fixes your tree, repeat until it does.

We never built this in BitKeeper but I should try. If for no other reason than to show people you can have the messy (but historically accurate) history under the covers but have a linear view that is pleasant for humans.

luckydude

9 tahun yang laludiscuss

I'm the guy who started this DAG model (also at Sun with NSElite and then later with BitKeeper).

I agree that rebase == centralized. It's a math thing. If you rebase and someone has a clone of your work prior to the rebase chaos happens when they come together. So you have to enforce a centralized flow to make it work in all cases. It's pretty much provable as in a math proof.

luckydude

9 tahun yang laludiscuss

Cool, glad you aren't pissed. And this whole thread has made me want to do a lmbench follow on paper, just get a new set of results for 2017 for *BSD, Linux, MacOS and maybe Solaris (does anyone care about anything other than Linux, MacOS, Windows these days?).

luckydude

9 tahun yang laludiscuss

But this is sort of like saying things would be so much better if we didn't have this annoying speed of light constraint. Yeah, if memory was all L3 instead of main memory, things would be faster, but it isn't.

Don't get me wrong, I'm all for primitives being light weight, that was the whole motivation behind writing lmbench. You and I agree on the goal.

Where we part ways is what is possible. When context switches are being done in the time it takes to do ~140 cache misses I don't see how it is possible to get to "much, much smaller". Smaller, sure, much smaller? How? Which cache misses are you going to not do?

What I'm looking for is actual insight into the problem. If you've looked at the code and you know the hardware and you know each cache miss on a first name basis and you are saying "right here, these 70 misses are not needed, we can get 2x better if we lose these", that's something that I and everyone would want to know. We already agree that less is more, the point is how do you get to less? Is it even possible?

Lemme run some numbers for i686 25 years ago. Back then, we were at about 34 cache misses/context switch. Now we are at about 140. So it would seem like there is some room there. But back then we didn't have the lock traffic we have today. And who knows what else they have shoved into the kernel. Lets ignore the lock traffic and extra bloat and say we could get back to 34 misses. That would get us to 2usecs rather than 7usecs. Which is better but does it meet your definition of "much, much smaller"?

That's where I'm coming from, I'm sizing the problem. I have no idea if they can shave it down to 34 misses, I very much doubt it. But I think we can agree that given the fact that the kernel is fine grained threaded they aren't going to get to better numbers than what they had when it wasn't threaded, right? That's a lower bound in practice, agreed? So if the cache miss fairy showed up and gave us our best case scenario we're about 3x faster. Which is nice but not life changing. And I don't believe for a second that there is 3x worth of easy to remove cache misses/bloat in that code path, Linus would have to be asleep at the wheel to allow that.

luckydude

9 tahun yang laludiscuss

Sorry if it sounds personal, it's not intended to be so. I get weird when I see people not seeing all of the picture. To me, the picture includes main memory, I've spent way too much time with a logic analyzer watching stuff go across the bus (actually did a lot of this while tuning some hashing code for performance).

Memory misses are a fact of life. If you look at my comments elsewhere, I noted that

    CPU: 20x faster
    Main memory: 3x faster
    Context switch: about the same

If memory wasn't the main part of the equation, shouldn't the context switches be faster? Yes, as I pointed out, the OS is now fine grained multi threaded but that doesn't explain a 20x difference.

As for the comment that some stuff is going to have zero cache misses, sure, in theory. Can you show any real world examples of that? I would think that anything that takes a lock on more than one cpu/cache is going to have lock traffic that is going to cause a cache miss like stall. Has cache coherency changed such that locks are "free"? That would be (interesting) news to me.

luckydude

9 tahun yang laludiscuss

You seem to be living in an imaginary world where main memory is much, much closer to the CPU than it is in real life. 10,000ns is 174 cache misses on my machine. That's not a lot of room when you are popping something off a queue or finishing an IO.

luckydude

9 tahun yang laludiscuss

You do realize the relative order of things, right? While a CPU instruction is around 1/4 of a ns, assuming a single cycle instruction which is not always the case, a memory load is ~60ns.

In order to really see if there is room for improvement one would need to take a look at each cache miss and see if that could be removed. On my machine, a simple context switch is 7.3us and a memory load is 57.4ns which means a total of 133 cache misses.

Could that be better? Sure, in theory. Could it be 10000x better? Not a chance. Not even if you made a zero cost context switch, you will still have cache misses getting there and coming back. Even if the context switch, the OS overhead, all of that were zero cost, if the two processes doing work have ~70 cache misses each then you are right back to where we are now.

It's 25 years later - what's changed? CPUs are 20x faster (.25ns clock instead of 5ns clock) but main memory is only ~3x faster. To the extent that things don't fit in the cache you would expect a 3x improvement in context switch time. Instead we have it almost the same speed (old was 6usec, current is 7usec). But the OS hasn't been held constant, it went from basically single threaded to scaling up to lots of CPUs. That scaling is not free, you are taking and releasing locks in your context switch code.

Personally, I doubt there is a lot of room for improvement. Some, sure. But I'd be astounded if you could figure out how to get a factor of two in Linux without losing something else.

luckydude

9 tahun yang laludiscuss

Um, you need to think more deeply about this. Yes, you can switch a "thread" (says the guy who wrote a user level thread package) very, very quickly but that's meaningless. Unless your application is one where all it does is context switch and does no other work.

"Context" is more than just the registers. You could make an instruction that did the context switch in zero time and a real context switch will take much more than zero time. Because there is more context than just the registers.

luckydude

9 tahun yang laludiscuss

Where are you getting milliseconds? Their results are right in line with what I'd expect, on the order of ~10-50 usecs.

luckydude

9 tahun yang laludiscuss

Replying to my own reply, I reread what they were doing and yeah, you are right, they do have basically the same procedure. My bad. Good on them for getting it (though I'll grumble that this was a solved problem, you can apt-get install it).

But you were right, looks the same. Sorry about that.

luckydude

9 tahun yang laludiscuss

The numbers are just a snapshot into history but what I measured and how it was measured is far more interesting. For example your comment "you've got basically the same procedure" isn'tquite right. If you read the paper, much effort was spent explaining to people that the baseline context switch is just a floor, what you will see in real life will be bigger since in real life a context switch is more that just a register file save/restore.

Very few benchmark writers get that point but that's sort of the main point. Not getting it means you are doomed to be mislead.

luckydude

9 tahun yang laludiscuss

> If the CPU made those an opcode instead of a wad of kernel code, the switch could be reduced to a clock cycle (ns?)

Not for any real world workload. It's worth reading section 6.6 of this: http://mcvoy.com/lm/bitmover/lmbench/lmbench-usenix.pdf

but I'll try and restate it here. So what's a context switch? Lots of people think it is putting one process to sleep and waking up another process. Which is sort of correct. Let's look at what that means. "Sleeping" a process means I have to take whatever hardware context there is and store it away (int/float registers are the basics). "Waking" a process is the opposite, go find the stored state, restore it, and return (sort of like longjmp()) to the awoken process.

But that is the minimal context switch, that's what you would have if you had a yield_to(pid_t pid) system call and you had a tight loop where pid A yields to pid B which yields to pid A, etc. Do that a million times, measure the total time, divide by a million.

That's not real world at all. In the real world your context is more than your registers, it is also your cache foot print. Pid A wasn't just yielding, it was doing some work. When it comes back, it has to either get lucky (with the right kind of cache that can hold more than one process's cache lines, look up physically vs virtually indexed caches, Hennessey & Patterson cover this nicely) or it has to reload state from L3 or main memory.

That's what the lmbench paper goes into a lot of detail about this. People write benchmarks and don't think about the fact that there is more to life than benchmarks. lmbench's context switch benchmarks are done as a function ctx(int N_processes, int working_set). Most people would benchmark ctx(2, 0) but that's nonsense unless you care about the silly yield/yield numbers. I dunno about you but when I'm debugging a perf problem, in ~30 years of doing that I have yet to see a perf problem around yield/yield (well, sort of. Oracle's distributed lock manager was as close as I've seen but even it had a larger context than zero bytes more than the register store/restore).

The interesting questions are:

- are your caches set up for multiple processes so you still have state when you switch back? - how many different processes can you have in the cache[s] at once? - how big is your OS path to sleep/wakeup, that uses up space in the instruction cache?

The lmbench paper talks about all this stuff, complete with crappy graphs written in troff/pic by yours truly that let you visualize when things will fit and when things will thrash.

luckydude

9 tahun yang laludiscuss

Did you read the posted article? It spends a lot of time trying to figure out how to measure context switches. Which I carefully wrote up around 1995 and still works to this day. That's independent of the hardware and was sort of my point. This is a solved problem.

And if you look at Table 10, the time for a context switch is remarkably similar to what it was 20 years ago (which means the OS is fatter, not surprising, it's scales up on SMPs now).

luckydude

9 tahun yang laludiscuss

Full results from mcvoy.com [email protected]:

                     L M B E N C H  2 . 0   S U M M A R Y
                     ------------------------------------
    
    
    Basic system parameters
    ----------------------------------------------------
    Host                 OS Description              Mhz
    --------- ------------- ----------------------- ----
    slovax.mc Linux 4.4.0-5   x86_64-glibc223-linux 3497
    
    Processor, Processes - times in microseconds - smaller is better
    ----------------------------------------------------------------
    Host                 OS  Mhz null null      open selct sig  sig  fork exec sh  
                                 call  I/O stat clos TCP   inst hndl proc proc proc
    --------- ------------- ---- ---- ---- ---- ---- ----- ---- ---- ---- ---- ----
    slovax.mc Linux 4.4.0-5 3497 0.09 0.12 0.28 1.76 2.170 0.12 0.58 86.4 249. 644.
    
    Context switching - times in microseconds - smaller is better
    -------------------------------------------------------------
    Host                 OS 2p/0K 2p/16K 2p/64K 8p/16K 8p/64K 16p/16K 16p/64K
                            ctxsw  ctxsw  ctxsw ctxsw  ctxsw   ctxsw   ctxsw
    --------- ------------- ----- ------ ------ ------ ------ ------- -------
    slovax.mc Linux 4.4.0-5 7.630 8.5200   10.5   10.9   15.5    10.8    19.0
    
    *Local* Communication latencies in microseconds - smaller is better
    -------------------------------------------------------------------
    Host                 OS 2p/0K  Pipe AF     UDP  RPC/   TCP  RPC/ TCP
                            ctxsw       UNIX         UDP         TCP conn
    --------- ------------- ----- ----- ---- ----- ----- ----- ----- ----
    slovax.mc Linux 4.4.0-5 7.630  13.6 14.7  20.8  19.4  25.8  24.5 25.8
    
    File & VM system latencies in microseconds - smaller is better
    --------------------------------------------------------------
    Host                 OS   0K File      10K File      Mmap    Prot    Page   
                            Create Delete Create Delete  Latency Fault   Fault 
    --------- ------------- ------ ------ ------ ------  ------- -----   ----- 
    slovax.mc Linux 4.4.0-5 2.7920 2.0480 8.2600 4.0840    17.6K 0.158 5.00000
    
    *Local* Communication bandwidths in MB/s - bigger is better
    -----------------------------------------------------------
    Host                OS  Pipe AF    TCP  File   Mmap  Bcopy  Bcopy  Mem   Mem
                                 UNIX      reread reread (libc) (hand) read write
    --------- ------------- ---- ---- ---- ------ ------ ------ ------ ---- -----
    slovax.mc Linux 4.4.0-5 1928 11.K 5674 43009M  11.0K  11.2K 7686.9 14.K 10.3K
    
    Memory latencies in nanoseconds - smaller is better
        (WARNING - may not be correct, check graphs)
    ---------------------------------------------------
    Host                 OS   Mhz  L1 $   L2 $    Main mem    Guesses
    --------- -------------  ---- ----- ------    --------    -------
    slovax.mc Linux 4.4.0-5  3497 0.889 2.6670   57.4

luckydude

9 tahun yang laludiscuss

Hey, same Joe from Sun? If so, howdy.

On my i7-5930K I'm seeing 7-10 usecs, quite a bit better than a millisecond. Linus cares about this stuff, I'd be very surprised if he didn't measure it regularly.

luckydude

9 tahun yang laludiscuss

I very much doubt it. If you read the paper, it took each of the things it could measure (memory, disk, network, etc) and measured bandwidth and latency. Those are pretty basic measurements and I suspect that they will still be interesting 100 years from now and measured in the same way.

I'm running the benchmark right now on a modern system just to see what it says. Yep, still works fine:

    "size=0k ovr=0.90
    2 7.63
    4 6.51
    8 7.78
    16 7.07
    24 7.78
    32 9.02
    64 10.35
    96 10.49

That says that a hot potato (I send a byte to you, you send it back to me, the time is the round trip for one pair) context switch is ~7 usecs. Do it in a ring with 96 processes and it goes up to ~10 usecs.

I think almost 100% of that benchmark is still valid (I say almost because there must be something that has bit rotted in 20+ years but I don't know of anything). It's worth a read.

Edit: formatting.

luckydude

9 tahun yang laludiscuss

Pretty sure that he's just rediscovering what I did in lmbench back in the early 1990's. All written up and open source (and got best paper in the 1995 Usenix):

http://mcvoy.com/lm/bitmover/lmbench/lmbench-usenix.pdf

Edit: which now that I think about it, was over 20 years ago. Reminds me of something a friend (Ron Minnich) said long ago: people rediscover stuff in computer science over and over, nobody wants to read old papers. Or something like that. He said it better, I think it was something like "want to look smart? Just take any 5 year old paper and redo whatever it did, our attention span seems to be very short."