Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Inline assembly in Linux

github.com

Post reply on HN
Print view View original

11–20 of 36 posts

Re: Inline assembly in Linux

#11

Post by nkurz »

brigade wrote: post #8
nkurz wrote: post #4

I've been using a lot of inline assembly lately, and while the Stockholm syndrome might be in effect, I'm coming to like the GCC syntax. For me, main thing that has helped has been to adopt a consistent syntax. Here's some examples of what I'm currently using for an AVX2 popcnt optimization, with some explanation. #define ASM_VEC_BYTE_COUNT_SET(vec, sum, mask, shuf) \ __asm volatile ("vpsrld $4, %[VEC], %[SUM]\n" \ "…

3 - using volatile for asm that doesn't have otherwise inexpressible side effects has the same askance that using it for thread safety has. If you think you need it, maybe you needed to add a "memory" clobber instead. 5 - I can't think of any meaning early clobber has on an input+output constraint ("+")? 6 - there are many cases where you really do want to give the compiler flexibility in addressing modes. Unfortunat…

re 3: If it were for correctness, I'd agree. But I don't need volatile to make it work, I need it to produce the assembly I want. If one instruction can execute only on Port 1 (popcnt) and the other can execute on Ports 0, 1, 5, or 6, there's sometimes a 50% performance difference based on the order two seemingly independent instructions are executed. Volatile also prevents the compiler from hoisting loads ahead of my inline assembly, which sometimes makes a difference. Clobbering "mem" might force other reloads that I don't want to happen.

re 5: Barring compiler bugs, I think you'd be right if correctness was the only issue. But I'm pretty sure I've sometimes solved problems by adding it, although this may have been when working around the POPCNT bug that added a false dependency on the output. It also might have been when reading and writing a variable multiple times?

re 6: In theory, yes. But usually in these cases you should be writing intrinsics or straight C instead of inline assembly. The place where this comes up most for me is when I have two variables that use the same index, and I want to ensure "DEC/JNZ" fusion at the end of the loop. If I let the compiler choose, it will find a way to defeat me by incrementing both array addresses. The other case is when you explicitly want a store to use Port 7 for address generation, which only happens without an index register.

re 7: Yes, I just personally find it more confusing because "x" fits so well with "XMM", and thus it feels odd to use it when you want only a "YMM". Also, see here for problems with a Clang and %q[VEC]: http://stackoverflow.com/questions/34459803/in-gnu-c-inline-...

re 4: Oops, I forgot to renumber. I had another comment suggesting that one always use the "V" VEX prefix on vector commands and the explicit output register, but deleted it because it seemed off topic.

Re: Inline assembly in Linux

#12

Post by sillysaurus3 »

haberman wrote: post #10
sillysaurus3 wrote: post #3

I'm trying to add call/cc to node, or to lua. Recap: call/cc is the ability to save the current state of a running thread, then revert to that state at a later point in time. In other words, at any point in your program, you can say "Save the current stack." It's saved as a function. Later, whenever you call that function, the current stack is thrown out, and replaced with the saved stack. This is very useful for a n…

> if your stack looks like Lua -> C -> Lua, then it won't work. I don't think you can safely solve this in the general case. There is a key problem I don't think you can work around. Say your stack looks like C(1) -> Lua -> C -> Lua. The outermost C frames might not know anything about Lua (they just use some library that uses Lua as a library). Say you try to take a snapshot of this stack to create a continuation. Y…

But what if C(1) and C(2) are not exactly the same size?

Say you want to resume continuation K, which has a stack of some size N.

The current thread has a stack of size M. If M >= N, everything is fine: you can safely overwrite the current stack with K's stack.

If M = N.

You could try to snapshot the entire C stack to get around this, including the outermost C frames.

Indeed! This is a solution.

It wouldn't be acceptable...

I like doing unacceptable things in my programs. It's the best part of programming, really.

There are a lot of solid arguments against call/cc. I think the most persuasive argument in favor of call/cc is that you become more powerful. Whatever metric you use to measure power, call/cc will improve it: Smaller code, less time spent writing code, and you can even write algorithms that you otherwise would not be able to.

Personally, I want call/cc in order to be able to use choose and fail. It's the ability to write programs that are guaranteed to never call fail(). pg explains it well:

"For example, this is a perfectly legitimate nondeterministic algorithm for discovering whether you have a known ancestor called Igor:

  Function Ig(n)
    if name(n) = ‘Igor’
      return n
    if parents(n)
      return Ig(choose(parents(n)))
    fail
The fail operator is used to influence the value returned by choose. If we ever encounter a fail, choose would have chosen incorrectly. By definition choose guesses correctly."

Call/cc makes this possible. There are a lot of fun things to do. The last few chapters of On Lisp show some particularly interesting sketches.

Re: Inline assembly in Linux

#13

Post by nkurz »

nafest wrote: post #7
nkurz wrote: post #4

I've been using a lot of inline assembly lately, and while the Stockholm syndrome might be in effect, I'm coming to like the GCC syntax. For me, main thing that has helped has been to adopt a consistent syntax. Here's some examples of what I'm currently using for an AVX2 popcnt optimization, with some explanation. #define ASM_VEC_BYTE_COUNT_SET(vec, sum, mask, shuf) \ __asm volatile ("vpsrld $4, %[VEC], %[SUM]\n" \ "…

I'd recommend to use intrinsics for SIMD vectorization, which is portable to platforms that don't support the GCC syntax (e.g. Windows with MSVC). You can use Intel's Intrinsics Guide ( https://software.intel.com/sites/landingpage/IntrinsicsGuide... ) to find the intrinsics that corresponds to the instructions you are using.

Yes, that's a great link, and I agree that if you can get the performance you want with Intrinsics they are usually a better choice. But if you need compiler-portable high performance, I find that it can be really hard to get good performance on GCC, ICC, and Clang simultaneously with intrinsics.

Another approach that's not quite there yet but is becoming more possible is to use https://www.cilkplus.org to annotate your C code to force automatic vectorization. It's native to ICC, built-in to GCC 5.0+, and available as an extension to Clang: https://news.ycombinator.com/item?id=11550250

Re: Inline assembly in Linux

#14

Post by haberman »

sillysaurus3 wrote: post #12
haberman wrote: post #10

Earlier quoted context omitted.

> if your stack looks like Lua -> C -> Lua, then it won't work. I don't think you can safely solve this in the general case. There is a key problem I don't think you can work around. Say your stack looks like C(1) -> Lua -> C -> Lua. The outermost C frames might not know anything about Lua (they just use some library that uses Lua as a library). Say you try to take a snapshot of this stack to create a continuation. Y…

But what if C(1) and C(2) are not exactly the same size? Say you want to resume continuation K, which has a stack of some size N. The current thread has a stack of size M. If M >= N, everything is fine: you can safely overwrite the current stack with K's stack. If M = N. You could try to snapshot the entire C stack to get around this, including the outermost C frames. Indeed! This is a solution. It wouldn't be accept…

> Say you want to resume continuation K, which has a stack of some size N.

The size of the continuation's stack doesn't matter for the problem I described, it's the size of the stack "underneath" your continuation that matters (ie. C(1) and C(2) above).

If C(2) > C(1) there is no way to shrink C(2) such that the continuation's stack can be copied into the right place.

> I like doing unacceptable things in my programs. It's the best part of programming, really.

What you do in your programs is up to you! But nobody else is going to use a C library that messes with the execution state of its callers (unless that is the point of the library, which it isn't with Lua).

Re: Inline assembly in Linux

#15

Post by sillysaurus3 »

haberman wrote: post #14
sillysaurus3 wrote: post #12

Earlier quoted context omitted.

But what if C(1) and C(2) are not exactly the same size? Say you want to resume continuation K, which has a stack of some size N. The current thread has a stack of size M. If M >= N, everything is fine: you can safely overwrite the current stack with K's stack. If M = N. You could try to snapshot the entire C stack to get around this, including the outermost C frames. Indeed! This is a solution. It wouldn't be accept…

> Say you want to resume continuation K, which has a stack of some size N. The size of the continuation's stack doesn't matter for the problem I described, it's the size of the stack "underneath" your continuation that matters (ie. C(1) and C(2) above). If C(2) > C(1) there is no way to shrink C(2) such that the continuation's stack can be copied into the right place. > I like doing unacceptable things in my programs…

I don't understand, but I'd like to.

To create a continuation, we need to copy the entire stack, by definition. But "the stack" is just an array of bytes. It's all the bytes between the current stack pointer and the "root" stack frame. So to create a continuation, copy these bytes and stash them somewhere, then set up a longjmp target to the current instruction.

To apply a continuation, i.e. to restore the stack, we overwrite the current stack starting from the root frame. Then we longjmp to where the continuation was originally created.

It seems like this scheme should work in any situation, but perhaps I'm missing something?

loeg pointed out getcontext(3) / setcontext(3), which seems promising. It looks like a standard way to sidestep all of this bookkeeping. It appears to be a high-level interface to the operations described above.

Lua is just a language, though. It's not "for" anything in particular.

Re: Inline assembly in Linux

#16

Post by haberman »

sillysaurus3 wrote: post #15
haberman wrote: post #14

Earlier quoted context omitted.

> Say you want to resume continuation K, which has a stack of some size N. The size of the continuation's stack doesn't matter for the problem I described, it's the size of the stack "underneath" your continuation that matters (ie. C(1) and C(2) above). If C(2) > C(1) there is no way to shrink C(2) such that the continuation's stack can be copied into the right place. > I like doing unacceptable things in my programs…

I don't understand, but I'd like to. To create a continuation, we need to copy the entire stack, by definition. But "the stack" is just an array of bytes. It's all the bytes between the current stack pointer and the "root" stack frame. So to create a continuation, copy these bytes and stash them somewhere, then set up a longjmp target to the current instruction. To apply a continuation, i.e. to restore the stack, we…

The Lua implementation is a C library. You invoke it by calling C functions like lua_call().

Imagine you have a C program like this:

    #include 

    int main() {
      for (int i = 0; i
Now imagine that internally, fancylib uses Lua. So fancylib_calculate() calls lua_call().

Now imagine that the Lua function run by fancylib decides to use continuations. When you call fancylib_calculate(0), it creates a continuation. And when you call fancylib_calculate(1), it decides to call the continuation.

If you restore the entire C stack to resume the Lua continuation, it will reset the loop in main() to i=0! Your program might end up printing val[0] over and over, in an infinite loop. This would be extremely surprising to you as the author of main(), because you were just trying to write a normal old for() loop. The Lua continuation should just restore the Lua-related stack, not the stack of the functions calling Lua!

Re: Inline assembly in Linux

#17

Post by aktau »

sillysaurus3 wrote: post #3

I'm trying to add call/cc to node, or to lua. Recap: call/cc is the ability to save the current state of a running thread, then revert to that state at a later point in time. In other words, at any point in your program, you can say "Save the current stack." It's saved as a function. Later, whenever you call that function, the current stack is thrown out, and replaced with the saved stack. This is very useful for a n…

I'm sure you aware you can implement call/1cc with Lua's coroutines: http://www.inf.puc-rio.br/~roberto/docs/MCC15-04.pdf. But maybe you want the full power of call/cc :).

Re: Inline assembly in Linux

#18

Post by sillysaurus3 »

haberman wrote: post #16
sillysaurus3 wrote: post #15

Earlier quoted context omitted.

I don't understand, but I'd like to. To create a continuation, we need to copy the entire stack, by definition. But "the stack" is just an array of bytes. It's all the bytes between the current stack pointer and the "root" stack frame. So to create a continuation, copy these bytes and stash them somewhere, then set up a longjmp target to the current instruction. To apply a continuation, i.e. to restore the stack, we…

The Lua implementation is a C library. You invoke it by calling C functions like lua_call(). Imagine you have a C program like this: #include int main() { for (int i = 0; i Now imagine that internally, fancylib uses Lua. So fancylib_calculate() calls lua_call(). Now imagine that the Lua function run by fancylib decides to use continuations. When you call fancylib_calculate(0), it creates a continuation. And when you…

If you restore the entire C stack to resume the Lua continuation, it will reset the loop in main() to i=0!

That's the point of continuations, though. That's a feature, not a bug. When you create a continuation, you're saying "whatever happens after this, allow me to do it again at some later time." If the calling library happened to be in a loop, then the goal is to serialize that loop so that it can be invoked again, at a later point.

If you keep applying the continuation in a loop, then you'll get an infinite loop. But if you invoke the continuation once, (and if subsequent calls to fancylib_calculate() don't), then you'll get the ability to print

  val[0] = 42
  val[1] = 99
  ...
  val[9] = 7
on demand. By invoking the continuation, you cause the loop to happen again.

In fact, you gain the ability to prevent the program from terminating, in a controlled fashion. Since you have access to the continuation, you can choose to invoke it on the 10th call to fancylib_calculate(), up to 3 times in a row. That would produce output like:

  val[0] = 42
  val[1] = 99
  ...
  val[9] = 7
  val[0] = 42
  val[1] = 99
  ...
  val[9] = 7
  val[0] = 42
  val[1] = 99
  ...
  val[9] = 7
then the program would exit.

Does that make sense? Apologies if we're talking past each other. I appreciate the patience.

Re: Inline assembly in Linux

#19

Post by [deleted] »

nkurz wrote: post #4

I've been using a lot of inline assembly lately, and while the Stockholm syndrome might be in effect, I'm coming to like the GCC syntax. For me, main thing that has helped has been to adopt a consistent syntax. Here's some examples of what I'm currently using for an AVX2 popcnt optimization, with some explanation. #define ASM_VEC_BYTE_COUNT_SET(vec, sum, mask, shuf) \ __asm volatile ("vpsrld $4, %[VEC], %[SUM]\n" \ "…

[deleted]

Re: Inline assembly in Linux

#20

Post by klodolph »

nkurz wrote: post #4

I've been using a lot of inline assembly lately, and while the Stockholm syndrome might be in effect, I'm coming to like the GCC syntax. For me, main thing that has helped has been to adopt a consistent syntax. Here's some examples of what I'm currently using for an AVX2 popcnt optimization, with some explanation. #define ASM_VEC_BYTE_COUNT_SET(vec, sum, mask, shuf) \ __asm volatile ("vpsrld $4, %[VEC], %[SUM]\n" \ "…

Cannot disagree more about #3. You almost never want asm volatile. The compiler is mostly doing data flow analysis, and I've seen so many programmers who don't understand that. So, if the compiler's data flow analysis doesn't put your asm block where you want, you just give up and put "volatile" on it. NO! Just let the compiler figure it out. You may be smarter about generating the assembly in this case, but the compiler is still very good at putting the assembly in the right place in your code. Usually, if I see "asm volatile" in someone's code, I step back and think "there's probably something wrong with the assembly" and I go back and read the manual on asm operand constraints, and then I find something wrong with the constraints. With the correct constraints / clobbers in place, my experience is that removing "volatile" only improves things.

Of course this is not true for synchronization primitives and the like.

Post reply on HN