5 ms·

What's weird about popcount?

Agingcoder 3y ago
That was my initial reaction as well. Counting bits arises quite naturally in many places.
tialaramex 3y ago
I'd guess to the "Surely my computer is a 1:1 mapping of the C programming language" people the expectation is that their CPU will have two increment instructions, two decrement instructions, and nothing like popcount. After all, C doesn't have a popcount operator. I have this terrible feeling that somewhere down the line we're going to get a generation of people who assumed the computer is a 1:1 mapping of Python -- a friend who teaches CS for a major university explained that they're going to teach Python as first language for Computer Science undergraduates starting 2024.
- automatic6131 3y ago
  Having python as a first programming language isn't a big disadvantage. The core elements of program optimization are still there: making sure you don't accidentally write O(n2) code etc. even if the memory management is opaque, you end up with an idea of values vs references, stacks and heaps just from some surprising edge cases in the language.
- mhh__ 3y ago
  I'm worried about python being assumed to be the same as every language than every CPU.
- jpc0 3y ago
  > a friend who teaches CS for a major university explained that they're going to teach Python as first language for Computer Science undergraduates starting 2024 I think this is significantly more common than you think it is. Also python has an extremely rich type system, can be completely duck typed as well, and does effectively everything you would need to know about in a CS degree, at least in the first semester or two, other than manual memory management. Which is significantly easier when you have a firm grasp of other aspects of programming. There are multiple approaches to teaching, starting with python and then moving lower down later isn't necessary a bad move. Who says starting with assembly/C and moving up is a good move?
  - ponderings 3y ago
    We could make a slow human friendly machine code, show how it abstracts electronic components and then get into physics and chemistry. It would be as fascinating as unproductive.
  - Philpax 3y ago
    > I think this is significantly more common than you think it is. For context: it was the first language taught in my CS degree in 2014. They switched to Python from Java due to its pedagogical advantages - namely, students being able to focus more on the high-level algorithmic semantics than on language design minutiae (Java) or memory management / poor diagnostics (C). I wasn't a fan of the decision at the time, but I certainly see why they did it in hindsight!
  - tialaramex 3y ago
    Oxford and Cambridge both begin with an ML, the same way I was taught last century (although of course it's a different ML today, I believe one of them uses Ocaml). Unavoidably I am biased, but I nevertheless feel confident that this is the correct way to teach programming to CS students in particular. One reason to use an ML, and especially to use a less common ML, is to create a level playing field. Teaching Python, Java (as they do today at his institution), or C (yes that happens) means some of the fresh students have months, maybe years, even occasionally decades of prior practical experience in the "first language" before day one. These students will find most, or even all, of the exercises trivial and so they won't actually learn what you were teaching, which may surprise them too, they're also likely to be disruptive, after all they're bored because this is easy. Now, for just a "level playing field" you could choose almost anything unpopular these days. Pascal? Scheme? Fortran? But that's not the only reason. MLs have a nice type system, which is great because probably simultaneously on the theory side of their course your students are learning about types, and Hindley–Milner gets you from a theory to a real world, from why this is a good idea, to huh, the machine did exactly what I meant, that's neat. If your colleagues are teaching them a sane approach to types, but you're teaching a language which says YOLO, everything is just a bag of bits don't worry about it, that's not a cohesive message. Likewise for function composition. It'd be nice if the first language you're teaching has actual bona fide mandatory TCO, so that when the nice elegant explanation in the theory class shows tail calls, the result in your practical class isn't a room full of stack overflow errors (or worse). This is reasonable for a First Language because you're expecting to teach these students several languages. The same doesn't apply to say, an optional module for Geographers that gets them enough Python to use a GIS competently. But we are (hopefully) not relying on Geographers to invent the next Python.
- eska 3y ago
  Maybe you’ll feel better knowing that popcount has been standardized in C23
  - tialaramex 3y ago
    Thanks, I didn't know about that and so I just read a summary, it's kind of sad that even the C standard library is now obliged put prefixes on names for namespace reasons, but yeah, it is good.
    - eska 3y ago
      To be fair it’s not different from C++ although it features namespaces. One still has to write “std::foo()” in headers in order to not pollute the global namespace, and therefore in template code, anyway. As long as they stop adding locale and global/thread-state dependent functions I’ll be quiet :)
      - sigsev_251 3y ago
        Regarding locale, let's hope that the text conversion API makes it in the next version so we can all work in unicode and be happy.
- larodi 3y ago
  Heh you underestimate (or perhaps understate) the predictability of stupidity... somewhere down the road you'll have kids running for-loops on top of GB-large LLM models :D now, seriously - it gets me thinking a lot that certain generation is going to be the last to be interested in assembly, but actually there are always people fascinated by the beauty of assembly language.
- RetroTechie 3y ago
  Well there have been Java bytecode & Forth optimized (if not directly executing) cpus. So you never know. ;-)
- sharikous 3y ago
  What would be so terrible? Some people will be naturally curious, as always, and they will go deeper. And even languages like Javascript influenced the design of CPUs and even specific instructions. Nothing is "pure" in the computing field
- praptak 3y ago
  > 1:1 mapping of the C programming language I was pretty surprised the first time I discovered the C compiler could "reverse engineer" a "logical or of two shifts" to generate a single rotate instruction.
  - tialaramex 3y ago
    Idiom recognition. Some compilers had idiom recognition before C existed, because in some of the early languages the literal interpretation of the common idioms is incredibly expensive to perform, but a compiler can recognise that actually it can take massive shortcuts. For example, sort this list of numbers into ascending order, then, take that sorted list, get the last number from it. With idiom recognition the compiler can say oh, I'll walk the list once, tracking the maximum as I go, that's much faster. In C this seems like, well, if I meant that I'd write that but I think APL is an example where the list expression is idiomatic and so that's what programmers will write but they want the fast thing.
- SeanLuke 3y ago
  > a friend who teaches CS for a major university explained that they're going to teach Python as first language for Computer Science undergraduates starting 2024. This is extremely widespread. My institution does it, as do many others I know of. I would not be surprised to find that Python is the most common initial programming language right now.
  - sgerenser 3y ago
    When I was in college (2001-2006) it was Java. I’m pretty sure the school already switched to Python for intro CS within the past few years.
- ilyt 3y ago
  > I have this terrible feeling that somewhere down the line we're going to get a generation of people who assumed the computer is a 1:1 mapping of Python -- a friend who teaches CS for a major university explained that they're going to teach Python as first language for Computer Science undergraduates starting 2024. Probably better than starting with C with all its footguns and "optimistic" approach to guessing what programmer meant...
adrian_b 3y ago
The only thing weird about it is that even if it was already implemented in the first commercial computer made with vacuum tubes, because its implementation in hardware is cheap and it can be much faster than a software implementation, it was omitted in most later computers, with the exception of the most expensive computers, which were typically used mainly by government agencies, until AMD decided to implement it in AMD Barcelona (2007). Once AMD had it, Intel followed soon in Nehalem (2009), and now most CPUs have it. The article is somewhat misleading about population count being available in ARM NEON since 2005 (i.e. since Cortex-A8). The 64-bit Armv8-A ISA, which was introduced in 2012, has the CNT instruction, which is indeed a population count instruction. The 32-bit Armv7-A ISA has the VCNT instruction, which is a variant of population count, but which is much less useful than the 64-bit POPCNT provided by Cray 1, AMD Barcelona, Intel Nehalem or Armv8-A, because it works only on 8-bit words, so executing the equivalent of a 64-bit POPCNT requires a sequence of several instructions.
- stassats 3y ago
  CNT on arm64 counts 8 or 16-bit elements too.
pwdisswordfishc 3y ago
Nothing. It's clickbait.

That was my initial reaction as well. Counting bits arises quite naturally in many places.

I'd guess to the "Surely my computer is a 1:1 mapping of the C programming language" people the expectation is that their CPU will have two increment instructions, two decrement instructions, and nothing like popcount. After all, C doesn't have a popcount operator. I have this terrible feeling that somewhere down the line we're going to get a generation of people who assumed the computer is a 1:1 mapping of Python -- a friend who teaches CS for a major university explained that they're going to teach Python as first language for Computer Science undergraduates starting 2024.

automatic6131 3y ago
Having python as a first programming language isn't a big disadvantage. The core elements of program optimization are still there: making sure you don't accidentally write O(n2) code etc. even if the memory management is opaque, you end up with an idea of values vs references, stacks and heaps just from some surprising edge cases in the language.
mhh__ 3y ago
I'm worried about python being assumed to be the same as every language than every CPU.
jpc0 3y ago
> a friend who teaches CS for a major university explained that they're going to teach Python as first language for Computer Science undergraduates starting 2024 I think this is significantly more common than you think it is. Also python has an extremely rich type system, can be completely duck typed as well, and does effectively everything you would need to know about in a CS degree, at least in the first semester or two, other than manual memory management. Which is significantly easier when you have a firm grasp of other aspects of programming. There are multiple approaches to teaching, starting with python and then moving lower down later isn't necessary a bad move. Who says starting with assembly/C and moving up is a good move?
- ponderings 3y ago
  We could make a slow human friendly machine code, show how it abstracts electronic components and then get into physics and chemistry. It would be as fascinating as unproductive.
- Philpax 3y ago
  > I think this is significantly more common than you think it is. For context: it was the first language taught in my CS degree in 2014. They switched to Python from Java due to its pedagogical advantages - namely, students being able to focus more on the high-level algorithmic semantics than on language design minutiae (Java) or memory management / poor diagnostics (C). I wasn't a fan of the decision at the time, but I certainly see why they did it in hindsight!
- tialaramex 3y ago
  Oxford and Cambridge both begin with an ML, the same way I was taught last century (although of course it's a different ML today, I believe one of them uses Ocaml). Unavoidably I am biased, but I nevertheless feel confident that this is the correct way to teach programming to CS students in particular. One reason to use an ML, and especially to use a less common ML, is to create a level playing field. Teaching Python, Java (as they do today at his institution), or C (yes that happens) means some of the fresh students have months, maybe years, even occasionally decades of prior practical experience in the "first language" before day one. These students will find most, or even all, of the exercises trivial and so they won't actually learn what you were teaching, which may surprise them too, they're also likely to be disruptive, after all they're bored because this is easy. Now, for just a "level playing field" you could choose almost anything unpopular these days. Pascal? Scheme? Fortran? But that's not the only reason. MLs have a nice type system, which is great because probably simultaneously on the theory side of their course your students are learning about types, and Hindley–Milner gets you from a theory to a real world, from why this is a good idea, to huh, the machine did exactly what I meant, that's neat. If your colleagues are teaching them a sane approach to types, but you're teaching a language which says YOLO, everything is just a bag of bits don't worry about it, that's not a cohesive message. Likewise for function composition. It'd be nice if the first language you're teaching has actual bona fide mandatory TCO, so that when the nice elegant explanation in the theory class shows tail calls, the result in your practical class isn't a room full of stack overflow errors (or worse). This is reasonable for a First Language because you're expecting to teach these students several languages. The same doesn't apply to say, an optional module for Geographers that gets them enough Python to use a GIS competently. But we are (hopefully) not relying on Geographers to invent the next Python.
eska 3y ago
Maybe you’ll feel better knowing that popcount has been standardized in C23
- tialaramex 3y ago
  Thanks, I didn't know about that and so I just read a summary, it's kind of sad that even the C standard library is now obliged put prefixes on names for namespace reasons, but yeah, it is good.
  - eska 3y ago
    To be fair it’s not different from C++ although it features namespaces. One still has to write “std::foo()” in headers in order to not pollute the global namespace, and therefore in template code, anyway. As long as they stop adding locale and global/thread-state dependent functions I’ll be quiet :)
    - sigsev_251 3y ago
      Regarding locale, let's hope that the text conversion API makes it in the next version so we can all work in unicode and be happy.
larodi 3y ago
Heh you underestimate (or perhaps understate) the predictability of stupidity... somewhere down the road you'll have kids running for-loops on top of GB-large LLM models :D now, seriously - it gets me thinking a lot that certain generation is going to be the last to be interested in assembly, but actually there are always people fascinated by the beauty of assembly language.
RetroTechie 3y ago
Well there have been Java bytecode & Forth optimized (if not directly executing) cpus. So you never know. ;-)
sharikous 3y ago
What would be so terrible? Some people will be naturally curious, as always, and they will go deeper. And even languages like Javascript influenced the design of CPUs and even specific instructions. Nothing is "pure" in the computing field
praptak 3y ago
> 1:1 mapping of the C programming language I was pretty surprised the first time I discovered the C compiler could "reverse engineer" a "logical or of two shifts" to generate a single rotate instruction.
- tialaramex 3y ago
  Idiom recognition. Some compilers had idiom recognition before C existed, because in some of the early languages the literal interpretation of the common idioms is incredibly expensive to perform, but a compiler can recognise that actually it can take massive shortcuts. For example, sort this list of numbers into ascending order, then, take that sorted list, get the last number from it. With idiom recognition the compiler can say oh, I'll walk the list once, tracking the maximum as I go, that's much faster. In C this seems like, well, if I meant that I'd write that but I think APL is an example where the list expression is idiomatic and so that's what programmers will write but they want the fast thing.
SeanLuke 3y ago
> a friend who teaches CS for a major university explained that they're going to teach Python as first language for Computer Science undergraduates starting 2024. This is extremely widespread. My institution does it, as do many others I know of. I would not be surprised to find that Python is the most common initial programming language right now.
- sgerenser 3y ago
  When I was in college (2001-2006) it was Java. I’m pretty sure the school already switched to Python for intro CS within the past few years.
ilyt 3y ago
> I have this terrible feeling that somewhere down the line we're going to get a generation of people who assumed the computer is a 1:1 mapping of Python -- a friend who teaches CS for a major university explained that they're going to teach Python as first language for Computer Science undergraduates starting 2024. Probably better than starting with C with all its footguns and "optimistic" approach to guessing what programmer meant...

adrian_b 3y ago

The only thing weird about it is that even if it was already implemented in the first commercial computer made with vacuum tubes, because its implementation in hardware is cheap and it can be much faster than a software implementation, it was omitted in most later computers, with the exception of the most expensive computers, which were typically used mainly by government agencies, until AMD decided to implement it in AMD Barcelona (2007). Once AMD had it, Intel followed soon in Nehalem (2009), and now most CPUs have it. The article is somewhat misleading about population count being available in ARM NEON since 2005 (i.e. since Cortex-A8). The 64-bit Armv8-A ISA, which was introduced in 2012, has the CNT instruction, which is indeed a population count instruction. The 32-bit Armv7-A ISA has the VCNT instruction, which is a variant of population count, but which is much less useful than the 64-bit POPCNT provided by Cray 1, AMD Barcelona, Intel Nehalem or Armv8-A, because it works only on 8-bit words, so executing the equivalent of a 64-bit POPCNT requires a sequence of several instructions.

stassats 3y ago
CNT on arm64 counts 8 or 16-bit elements too.

pwdisswordfishc 3y ago

Nothing. It's clickbait.