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

Is This a Branch?

bartwronski.com

Post reply on HN
Print view View original

71–78 of 78 posts

Re: Is This a Branch?

#71

Post by RHSeeger »

Pxtl wrote: post #69
RHSeeger wrote: post #30

Earlier quoted context omitted.

When I find a place where a complex ternary is probably the best choice, I'm a big fan of the following format, because I find it clear that each line is a new condition myvar = condition_1 ? value_1 : condition_2 ? value_2 : condition_3 ? value_3 : value_fallback;

And, to illustrate my point, hypothetical "if statement is also conditional expression" syntax, to illustate how much more readable "ifs" are than "?:": myvar = if(condition_1) {value_1} else if(condition_2) {value_2} else if(condition_3) {value_3} else {value_fallback};

While I agree that "if statements are expressions" is a nice feature, I disagree that your version is more readable. That being said, it's readable enough that, if the rest of my team preferred it, I'd be ok using it.

Re: Is This a Branch?

#72

Post by wizzwizz4 »

atty wrote: post #68
wizzwizz4 wrote: post #51

Earlier quoted context omitted.

I've been designing a programming language where nothing is a side-effect – including calling conventions, processor caches, branch predictors, locks, graphics modes, etc.. “Runtime has to be independent of the value of the input” would be how that language expresses "constant time" – and it would take into account every part of the compiler's model of the target architecture (which, by the way, is also described in…

Unless I’m misunderstanding your point, I don’t think what you want is possible, due to microcode. You give the AMD/Intel/Arm/etc platform some instructions to execute, and then they execute it in ways that are not guaranteed to stay the same, between microcode updates and between hardware revisions. The only guarantee is that the results you get should be the same as if the instructions you requested were executed i…

The sophisticated version is difficult, but there are a lot of things you can treat as "opaque, everything mutates this, lots of stuff depends on it" and still be able to make decent optimisations based on what you know.

Re: Is This a Branch?

#73

Post by sherbert-santa »

wizzwizz4 wrote: post #65
pjc50 wrote: post #56

Earlier quoted context omitted.

> processor caches, branch predictors You can't "take this into account" because it requires state that isn't visible to you and also requires you to know the design of future hardware!

It requires state that can be inferred and manipulated. For the cache, assuming you know how large the cache is, you can just fill up the cache with useless pages, evicting whatever might be vulnerable to a timing attack, before having it loaded back in. Very slow , but it works. (You might be able to get away with less, depending on the OS's guarantees and what you can assume about how your program will run – and th…

No. You cannot infer the layout of the cache based on size alone. You don’t know how many ways there are, how many sets their are etc. you don’t even know their LRU scheme.

For mutating branch predictor state at will, you will need your compiler to write self modifying cache. This will pollute the icache and further mutate the state based on where the cache line lies, and the current state of the icache.

You could maybe restrict your target to open source hardware and come up with something.

Re: Is This a Branch?

#74

Post by progval »

lmm wrote: post #3

Ifs are generally bad for readability though, because they force the reader to understand your control flow. Replacing an if with a ternary makes it more readable, not because the generated code is any different, but because a reader immediately knows that they don't need to scan through the two sides for control flow constructs (because the two sides of the ternary are guaranteed to be expressions rather than blocks…

> because the two sides of the ternary are guaranteed to be expressions rather than blocks

But expressions can contain blocks. Therefore, this is valid:

    int main(void) {
        while (1) {
            1 ? ({ break; }) : ({ break; });
        }
    }
The right way to easily spot control flow construct is syntax highlighting.

Re: Is This a Branch?

#75

Post by lispm »

_ph_ wrote: post #63
lispm wrote: post #58

Earlier quoted context omitted.

Many Lisp compilers do that. What makes SBCL special is a) using type information as compile-time assertions and b) the level of diagnostic output during compilation. The compiler explains in detail when operations can't be optimized further, for example because of lack of type information.

Well, yes. How SBCL uses the type annotations as well as type inferencing to completely eliminate type checking throughout sections of code and generating highly efficient assembly code makes looking at the assembly output of SBCL especially interesting to look at. It gives you good feedback whether your type annotations had the desired optimization outcomes. I didn't want to indicate that other Lisp implementations…

Many implementations also give us type inferencing and optimizations, but usually not compile time type checking like in SBCL. I would also kind of think that the level of type inferencing in SBCL is greater.

Re: Is This a Branch?

#76

Post by sherbert-santa »

sherbert-santa wrote: post #73
wizzwizz4 wrote: post #65

Earlier quoted context omitted.

It requires state that can be inferred and manipulated. For the cache, assuming you know how large the cache is, you can just fill up the cache with useless pages, evicting whatever might be vulnerable to a timing attack, before having it loaded back in. Very slow , but it works. (You might be able to get away with less, depending on the OS's guarantees and what you can assume about how your program will run – and th…

No. You cannot infer the layout of the cache based on size alone. You don’t know how many ways there are, how many sets their are etc. you don’t even know their LRU scheme. For mutating branch predictor state at will, you will need your compiler to write self modifying cache. This will pollute the icache and further mutate the state based on where the cache line lies, and the current state of the icache. You could ma…

Self modifying *code

Re: Is This a Branch?

#77

Post by wizzwizz4 »

sherbert-santa wrote: post #73
wizzwizz4 wrote: post #65

Earlier quoted context omitted.

It requires state that can be inferred and manipulated. For the cache, assuming you know how large the cache is, you can just fill up the cache with useless pages, evicting whatever might be vulnerable to a timing attack, before having it loaded back in. Very slow , but it works. (You might be able to get away with less, depending on the OS's guarantees and what you can assume about how your program will run – and th…

No. You cannot infer the layout of the cache based on size alone. You don’t know how many ways there are, how many sets their are etc. you don’t even know their LRU scheme. For mutating branch predictor state at will, you will need your compiler to write self modifying cache. This will pollute the icache and further mutate the state based on where the cache line lies, and the current state of the icache. You could ma…

> You cannot infer the layout of the cache based on size alone.

No – but the compiler would presumably be told how the specific processor's cache works. If it's possible for a human to write cache-flushing code, it's possible to describe it to a computer. (And that was just an example.)

> For mutating branch predictor state at will, you will need your compiler to write self modifying code.

Only for arbitrary modifications. For specific modifications, it's fine to go with ordinary code – though self-modifying code isn't actually all that hard to model, if you generalise “state” to also encompass the state of the self-modifying section. (Compilers already have “all branches” type things.)

> You could maybe restrict your target to open source hardware

There's no need to make this restriction. You only need sufficiently-understood hardware; you underestimate the ability of reverse-engineers.

Re: Is This a Branch?

#78

Post by sherbert-santa »

wizzwizz4 wrote: post #77
sherbert-santa wrote: post #73

Earlier quoted context omitted.

No. You cannot infer the layout of the cache based on size alone. You don’t know how many ways there are, how many sets their are etc. you don’t even know their LRU scheme. For mutating branch predictor state at will, you will need your compiler to write self modifying cache. This will pollute the icache and further mutate the state based on where the cache line lies, and the current state of the icache. You could ma…

> You cannot infer the layout of the cache based on size alone. No – but the compiler would presumably be told how the specific processor's cache works. If it's possible for a human to write cache-flushing code, it's possible to describe it to a computer. (And that was just an example.) > For mutating branch predictor state at will, you will need your compiler to write self modifying code. Only for arbitrary modifica…

How exactly would you modify branch predictor state without self modifying code? I am very interested in this.

Another major question: a lot of x86 ops for manipulating things you want to manipulate are ring 0 instructions.

We haven’t even discussed the effect of somewhat non deterministic delays caused by contention from other processes. This can change the true execution order of instruction inside the pipes, even if you somehow manage to enforce in order issue.

Post reply on HN