92 ms·

I'm surprised the "capitalizing a 32 character string" example is actually one second faster than adding two 32bit integers. Still super slow, but I'm curious w

I'm surprised the "capitalizing a 32 character string" example is actually one second faster than adding two 32bit integers. Still super slow, but I'm curious why. I'd assume that if the string_cap.cc example takes 256 wires, wouldn't add.cc take 64 wires?

deleted 4y ago
[deleted]
j2kun 4y ago
Short answer: string cap has more parallelism in the circuit. Depth is more important than total number of gates, and optimizers can decrease depth pretty well.
- squeaky-clean 4y ago
  Thanks (and Dylan18607). So to continue assuming, the number of wires specified is just the input/output, and the add.cc has more intermediate "wires"?
  - j2kun 4y ago
    It's more like: to implement add you need a ripple carry adder. You can't evaluate bit 6 until you've evaluated bits 1-5. So there's a nested dependence that makes the circuit deep. String cap, on the other hand, can be implemented in parallel by looking at pairs of characters independently. So that makes it into a parallel band of small circuits, which we can evaluate in different CPU cores. Also I think the capitalization operation also affects fewer bits of a char (it's just toggling one bit in each char, IIRC).
    - anthk 4y ago
      It's faster to carry six glasses at once than having to carry them to some point one by one.
    - squeaky-clean 4y ago
      That makes perfect sense, thank you! I also didn't know until today that capitalization in ascii is just the 6th bit. I thought it would have been doing 32 subtract operations. (I'll be honest I haven't written my own uppercase function since school haha)
Dylan16807 4y ago
Since it encrypts one bit at a time, does capitalizing even have to touch the 224 bits that don't change? > wouldn't add.cc take 64 wires? Plus another hundred intermediate wires. And it's doing more complicated operations, however much that matters.
- squeaky-clean 4y ago
  No idea lol! Though it says it works on all 32 bytes in parallel regardless of input size. I imagine ignoring the bits that don't change would be some sort of security vulnerability? You could probably work out some timing attack or entropy reduction otherwise? They state it should take the same duration regardless of the length of the input string or how much needs to be capitalized (all branches are executed even though many are discarded)
  - Dylan16807 4y ago
    > I imagine ignoring the bits that don't change would be some sort of security vulnerability? You could probably work out some timing attack or entropy reduction otherwise? Nah. The bits are hardcoded into the circuit to not change. That's part of the program, and the program is public information. Only bit 6 of each byte might change, and everyone knows it.
    - squeaky-clean 4y ago
      Whoa, I never knew about the ascii 6th bit trick, I've never really considered capitalization wasn't some random offset. So that does make this circuit simpler than I thought it was, and there's the parallelism aspect. It's not so surprising now that it's faster than the add.

deleted 4y ago

[deleted]

j2kun 4y ago

Short answer: string cap has more parallelism in the circuit. Depth is more important than total number of gates, and optimizers can decrease depth pretty well.

squeaky-clean 4y ago
Thanks (and Dylan18607). So to continue assuming, the number of wires specified is just the input/output, and the add.cc has more intermediate "wires"?
- j2kun 4y ago
  It's more like: to implement add you need a ripple carry adder. You can't evaluate bit 6 until you've evaluated bits 1-5. So there's a nested dependence that makes the circuit deep. String cap, on the other hand, can be implemented in parallel by looking at pairs of characters independently. So that makes it into a parallel band of small circuits, which we can evaluate in different CPU cores. Also I think the capitalization operation also affects fewer bits of a char (it's just toggling one bit in each char, IIRC).
  - anthk 4y ago
    It's faster to carry six glasses at once than having to carry them to some point one by one.
  - squeaky-clean 4y ago
    That makes perfect sense, thank you! I also didn't know until today that capitalization in ascii is just the 6th bit. I thought it would have been doing 32 subtract operations. (I'll be honest I haven't written my own uppercase function since school haha)

Dylan16807 4y ago

Since it encrypts one bit at a time, does capitalizing even have to touch the 224 bits that don't change? > wouldn't add.cc take 64 wires? Plus another hundred intermediate wires. And it's doing more complicated operations, however much that matters.

squeaky-clean 4y ago
No idea lol! Though it says it works on all 32 bytes in parallel regardless of input size. I imagine ignoring the bits that don't change would be some sort of security vulnerability? You could probably work out some timing attack or entropy reduction otherwise? They state it should take the same duration regardless of the length of the input string or how much needs to be capitalized (all branches are executed even though many are discarded)
- Dylan16807 4y ago
  > I imagine ignoring the bits that don't change would be some sort of security vulnerability? You could probably work out some timing attack or entropy reduction otherwise? Nah. The bits are hardcoded into the circuit to not change. That's part of the program, and the program is public information. Only bit 6 of each byte might change, and everyone knows it.
  - squeaky-clean 4y ago
    Whoa, I never knew about the ascii 6th bit trick, I've never really considered capitalization wasn't some random offset. So that does make this circuit simpler than I thought it was, and there's the parallelism aspect. It's not so surprising now that it's faster than the add.