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

Branch predictor: How many “if”s are too many?

blog.cloudflare.com

Post reply on HN
Print view View original

101–109 of 109 posts

Re: Branch predictor: How many “if”s are too many?

#101

Post by Dylan16807 »

BenjiWiebe wrote: post #100
Dylan16807 wrote: post #96

Earlier quoted context omitted.

Sloppy code would be using the wrong data structures and algorithms. Sloppy code would be optimizing nothing at all. If you write things with good big O performance, for almost all of your lines of code you're done. It will perform fine. Bloated messes don't come from writing a bunch of business logic in python instead of C, not while processors are this many orders of magnitude faster than they used to be. They come…

But if you're processing 10's of thousands of records in an O(n) loop, it will still be 10's of thousands of times slower than processing a single record in that loop. i.e. having good big O still doesn't mean the code will be fast.

Are you saying this is a scenario where O(1) is possible? Then "good big O" is O(1). Code that is O(n) is a mistake.

If you're saying the fastest method is O(n), then sure, no method can guarantee fast processing of the entire list. But that fact sure isn't python's fault!

Re: Branch predictor: How many “if”s are too many?

#102

Post by gaul »

Denvercoder9 wrote: post #55
majke wrote: post #8

Earlier quoted context omitted.

Modern freshest gcc 11 can optimize the if's nicely https://godbolt.org/z/771foExcG getCountry: mov eax, OFFSET FLAT:.LC0 cmp edi, 258 ja .L1 mov edi, edi mov rax, QWORD PTR CSWTCH.1[0+rdi*8] .L1: ret

Anyone know what the purpose of the mov edi, edi instruction there is? Edited to add: I understand that it's a NOP, but why would the compiler emit one here?

This is not a NOP; it explicitly clears the upper 32 bits of EDI since the compiler does not know that they are zero in this situation. If you change cc from an int to size_t (long on x86-64) the compiler will generate:

        mov     eax, OFFSET FLAT:.LC0
        cmp     rdi, 258
        ja      .L1
        mov     rax, QWORD PTR CSWTCH.1[0+rdi*8]
Note that in some cases the compiler can do this automatically via lifetime analysis but not in this freestanding example.

Re: Branch predictor: How many “if”s are too many?

#103

Post by Too »

flakiness wrote: post #59

In old days people used #ifdef to compile things out so that the "production code" doesn't have any unnecessary branches. I was shocked when I first saw these living if()s in the server-side C++ code but then realized it was vital for debugging in production. People also used to prefer table based jump over long if-else-if chain for anecdotal performance reasons. That has gradually changed over the evolution of CPUs…

I think ifs based on constants get optimized to nothing anyway. So really no need to use #ifdef.

Re: Branch predictor: How many “if”s are too many?

#104

Post by jugg1es »

Agentlien wrote: post #90
jugg1es wrote: post #21

This is a pretty amazing analysis that answers questions we probably all had as newbie programmers before realizing that code readability mattered more than efficiency 99.9% of the time.

This kind of statement always makes me feel funny. It's true that algorithmic complexity is the most important part, you always have to measure, and micro optimisations are often not worthwhile. But this type of statement seems a lot stronger than that. I'm a graphics programmer working in game development and most of my time is spent on our performance task force. I spend a lot of time thinking about the performance…

Your job is very different than mine. Gaming/graphics are their own domain with different priorities. When your goal is to process data on the scale of several seconds, readability matters more. When your goal is performance per frame, you will definitely have different priorities.

Re: Branch predictor: How many “if”s are too many?

#105

Post by TechHypes »

Extraordinary" rel="nofollow">https://www.techhypes.com/top-5-best-gaming-keyboards-in-may... article, just to add a certain something: restrictive branches can truly play with the compiler's capacity to enhance, particularly the capacity to auto-vectorize. So regardless of whether a never-taken branch is pretty much free when the CPU executes it, simply having it there may have brought about substantially less proficient codegen. Simply something more to remember with this issue.

Re: Branch predictor: How many “if”s are too many?

#106

Post by jfrunyon »

sellyme wrote: post #84
jfrunyon wrote: post #41

> This is visible with block size 64 breaking at 3072 mark 3072 64=196K, and for block 32 at 6144: 6144 32=196K. You mean 192K.

They mean 196K, aka 196 thousand. You mean 192KB.

No, they mean 192KB. Because that's how they refer to it literally every other time. Oh, and because it's NOT 196 thousand. 3072*64 = 196608. Which rounds to... 197 thousand. (But is exactly 192KB - or 192KiB if you prefer that sort of thing)

Re: Branch predictor: How many “if”s are too many?

#107

Post by jfrunyon »

jfrunyon wrote: post #41

> This is visible with block size 64 breaking at 3072 mark 3072 64=196K, and for block 32 at 6144: 6144 32=196K. You mean 192K.

Markdown is a lovely and amazing solution to text formatting. Formatting fixed below:

> This is visible with block size 64 breaking at 3072 mark 3072*64=196K, and for block 32 at 6144: 6144*32=196K.

You mean 192K.

Re: Branch predictor: How many “if”s are too many?

#108

Post by sellyme »

jfrunyon wrote: post #106
sellyme wrote: post #84

Earlier quoted context omitted.

They mean 196K, aka 196 thousand. You mean 192KB.

No, they mean 192KB. Because that's how they refer to it literally every other time. Oh, and because it's NOT 196 thousand. 3072*64 = 196608. Which rounds to... 197 thousand. (But is exactly 192KB - or 192KiB if you prefer that sort of thing)

> No, they mean 192KB. Because that's how they refer to it literally every other time.

Are you suggesting that you believe that both the number and the unit were a typo?

> Oh, and because it's NOT 196 thousand. 3072*64 = 196608. Which rounds to... 197 thousand.

Truncation is a totally valid way of representing numbers when pinpoint accuracy isn't really necessary. "32K" is a very common way to refer to the number 32768, for example.

> or 192KiB if you prefer that sort of thing

I appreciate the caveat here as I very much do not and believe that the concept of kibibytes being distinct from kilobytes are a scam perpetuated by hard-drive and floppy disk manufacturers as a way to cut costs while still advertising the same storage space. It definitely makes sense to use the same definitions for the SI prefixes, but even two decades after that ISO was published no-one actually says "kibibytes", so clearly it's not much of a standard.

But that's another discussion entirely.

Re: Branch predictor: How many “if”s are too many?

#109

Post by jfrunyon »

sellyme wrote: post #108
jfrunyon wrote: post #106

Earlier quoted context omitted.

No, they mean 192KB. Because that's how they refer to it literally every other time. Oh, and because it's NOT 196 thousand. 3072*64 = 196608. Which rounds to... 197 thousand. (But is exactly 192KB - or 192KiB if you prefer that sort of thing)

> No, they mean 192KB. Because that's how they refer to it literally every other time. Are you suggesting that you believe that both the number and the unit were a typo? > Oh, and because it's NOT 196 thousand. 3072*64 = 196608. Which rounds to... 197 thousand. Truncation is a totally valid way of representing numbers when pinpoint accuracy isn't really necessary. "32K" is a very common way to refer to the number 327…

> I appreciate the caveat here as I very much do not and believe that the concept of kibibytes being distinct from kilobytes are a scam perpetuated by hard-drive and floppy disk manufacturers as a way to cut costs while still advertising the same storage space

Except that you just said that "32768->32K" involves truncation. What is 32*1024? 32 KiB is exactly, no truncation involved, 32768.

(BTW, kibibytes are distinct from kilobytes because 1024 is distinct from 1000. Similarly, 1048576 is distinct from 1000000.)

> Truncation is a totally valid way of representing numbers [with lower precision]

No. Rounding is.

--

Once again. THEY, the authors of the post, use unit multipliers of 1024 in every other figure on the page. Except in this one particular figure where you claim they intentionally use 1000. I frankly don't care whether they define KB as 1000B or 1024B. Either way works. But they should, at the very least, be consistent within the space of a single blog post.

Post reply on HN