9 ms·

Implementing ‘strlen’ using SVE

109 points by ibobev 4y ago

deleted 4y ago
[deleted]
saagarjha 4y ago
> Thankfully, SVE comes with a load instruction that would only fault on the ‘first active element’: as long as the first element you are loading is valid, then there is no fault. Huh, this is an interesting instruction. Wonder if this will “break” code that expected a read into an unmapped page to fault…
- colejohnson66 4y ago
  Also, what is actually loaded for the fault-suppressed portion? According to some documentation[0], anything after the first element uses the `MemNF` "intrinsic": if first then // Mem[] will not return if a fault is detected for the first active element data = Mem[addr, mbytes, AccType_NORMAL]; first = FALSE; else // MemNF[] will return fault=TRUE if access is not performed for any reason (data, fault) = MemNF[addr, mbytes, AccType_CNOTFIRST]; However, if the data would fault, said "intrinsic"[1] returns `UNKNOWN` for the data: (value<7:0>, bad) = MemSingleNF[address, 1, acctype, aligned]; if bad then return (bits(8*size) UNKNOWN, TRUE); But clearly, the value of `UNKNOWN` is visible to the program, so what is it? I'd assume it would either be zeros or whatever the previous scalar was (i.e. untouched), but does anyone know? [0]: http://hehezhou.cn/isa/ldff1b_z_p_br.html http://hehezhou.cn/isa/ldff1b_z_p_br.html [1]: http://hehezhou.cn/isa/shared_pseudocode.html#impl-aarch64.MemNF.read.3 http://hehezhou.cn/isa/shared_pseudocode.html#impl-aarch64.M...
  - haimez 4y ago
    Fingers crossed for the answer to be “zeros” and not “zeros, timing variable if attempting to access the values” or “zeros, timing variable if read spans into unmapped region”. Certainly, “contents of unmapped region” wouldn’t be on the table these days, right?
    - planede 4y ago
      I wonder if the possibilities include "garbage, from some other register due to register renaming". Certainly not data leaked from some unmapped memory, but it can still be garbage.
  - brigade 4y ago
    The CONSTRAINED UNPREDICTABLE handling - it's effectively implementation defined, but ARM constrains the implementations to always choose one of 4 possibilities: - Whether subsequent non-faulting elements are loaded as normal, or ignored and treated as also faulting (more relevant for the FF gather variants) - Whether the faulting elements zero or merge the previous element value of the destination vector
  - unwind 4y ago
    Great links, thanks! The first one has an awesome typo (I hope, else they're being a bit evil) with a double negative in the text explaining the instruction: Inactive elements will not not cause a read from Device memory or signal a fault, and are set to zero in the destination vector. Note the double "not" in the first half. Ouch.
  - Tuna-Fish 4y ago
    > I'd assume it would ... be ... whatever the previous scalar was (i.e. untouched) It is a fair assumption these days that no instruction leaves bits in the register "untouched" unless doing so is a core part of what's needed for the instruction to work. On architectures with register renaming (which is all high-performance architectures) it can be surprisingly expensive. The very least, it forces a dependency on all previous instructions that write that register, and adds another source operand to the instruction. And on most real architectures, this source operand would be required to be present before the instruction itself can start. This is particularly bad for load instructions, if it pushes back when the load can be submitted to cache. This can wipe out all your memory parallelism, and effectively cut your performance to a fraction of what it would othewise be. The basic mental model you need to have is that every instruction that writes to a register always gets a new register that starts with all bits zeroed. To have anything else, you have to do work.
- runehol 4y ago
  This case is handled correctly. SVE loops don't count up a fixed number of elements per loop iteration, instead they count up the number of elements set in the predicate register. If you perform a page-crossing load where, say, only elements 0-5 out of 32 elements are loaded, then only elements 0-5 in the predicate register gets set, the loop steps 6 elements instead of 32 elements in this iteration. On the next time around, if you really intended to go past the end, byte 0 of the next page will be in the first element position and goes through normal fault handling. Lemire's example loop is subtly wrong here, but the version in the SVE slides he links to is fine.
blake1 4y ago
Always amusing when the assembly language version is so much terser than the C version.
- dvhh 4y ago
  Isn't that the goal of higher level language to start with ?
  - gaganyaan 4y ago
    I think you read their comment backwards? I'd expect the higher level language to be terser in most scenarios.
- zamadatix 4y ago
  Feels like cheating to say that about a function written in intrinsics though.
- sebazzz 4y ago
  Yes, but some x64 compilers like Microsoft Visual C++ don't allow raw assembly in C++ (it did allow it for x86-32 though)
  - my123 4y ago
    Not allowed for MSVC on arm and arm64 too.
- Liquid_Fire 4y ago
  To be fair, the assembly version seems to be missing about half the function, so it's not exactly a fair comparison.
Gigachad 4y ago
Why does C not just store the length of the string before the string itself?
- vlovich123 4y ago
  Probably a historical artifact from when the extra 4-8 bytes required posed a serious overhead. The other advantage is that there’s nothing involved in porting C strings between 8, 16, 32, and 64 bit machines. Of course, most modern languages will store the length separately (using small string optimization) AND offer a way to convert to a C string (for OS interop). There’s an argument that taking a substring off a C string a) can be done without allocating a copy b) can be done with pure pointer manipulation. In practice though I’m not sure how critical that case is.
  - cplusplusfellow 4y ago
    This could also be achieved by locating the pointer and the (offset and length) as separate.
    - stevefan1999 4y ago
      This will cause a lot of indirect access which can be a problem in the 70s-80s' because this not only requires more memory but this also requires many more operations (say like LEA) to extract a slice. This might work fine in a bank mainframe, but is prohibitively expensive in the minicomputers back in the days. C is written for Unix. Unix is written with minicomputers in mind. Thus C is somewhat influenced by minicomputers and has to work on their setback in the good ol' days. You have to think in the historic context.
      - masklinn 4y ago
        > This will cause a lot of indirect access It causes strictly less indirect access if you store it as part of the string struct, as C++, Go, or Rust do.
synergy20 4y ago
c++ string has size meta info builtin so you no longer need strlen?

109 points by ibobev 4y ago

deleted 4y ago

[deleted]

> Thankfully, SVE comes with a load instruction that would only fault on the ‘first active element’: as long as the first element you are loading is valid, then there is no fault. Huh, this is an interesting instruction. Wonder if this will “break” code that expected a read into an unmapped page to fault…

colejohnson66 4y ago
Also, what is actually loaded for the fault-suppressed portion? According to some documentation[0], anything after the first element uses the `MemNF` "intrinsic": if first then // Mem[] will not return if a fault is detected for the first active element data = Mem[addr, mbytes, AccType_NORMAL]; first = FALSE; else // MemNF[] will return fault=TRUE if access is not performed for any reason (data, fault) = MemNF[addr, mbytes, AccType_CNOTFIRST]; However, if the data would fault, said "intrinsic"[1] returns `UNKNOWN` for the data: (value<7:0>, bad) = MemSingleNF[address, 1, acctype, aligned]; if bad then return (bits(8*size) UNKNOWN, TRUE); But clearly, the value of `UNKNOWN` is visible to the program, so what is it? I'd assume it would either be zeros or whatever the previous scalar was (i.e. untouched), but does anyone know? [0]: http://hehezhou.cn/isa/ldff1b_z_p_br.html http://hehezhou.cn/isa/ldff1b_z_p_br.html [1]: http://hehezhou.cn/isa/shared_pseudocode.html#impl-aarch64.MemNF.read.3 http://hehezhou.cn/isa/shared_pseudocode.html#impl-aarch64.M...
- haimez 4y ago
  Fingers crossed for the answer to be “zeros” and not “zeros, timing variable if attempting to access the values” or “zeros, timing variable if read spans into unmapped region”. Certainly, “contents of unmapped region” wouldn’t be on the table these days, right?
  - planede 4y ago
    I wonder if the possibilities include "garbage, from some other register due to register renaming". Certainly not data leaked from some unmapped memory, but it can still be garbage.
- brigade 4y ago
  The CONSTRAINED UNPREDICTABLE handling - it's effectively implementation defined, but ARM constrains the implementations to always choose one of 4 possibilities: - Whether subsequent non-faulting elements are loaded as normal, or ignored and treated as also faulting (more relevant for the FF gather variants) - Whether the faulting elements zero or merge the previous element value of the destination vector
- unwind 4y ago
  Great links, thanks! The first one has an awesome typo (I hope, else they're being a bit evil) with a double negative in the text explaining the instruction: Inactive elements will not not cause a read from Device memory or signal a fault, and are set to zero in the destination vector. Note the double "not" in the first half. Ouch.
- Tuna-Fish 4y ago
  > I'd assume it would ... be ... whatever the previous scalar was (i.e. untouched) It is a fair assumption these days that no instruction leaves bits in the register "untouched" unless doing so is a core part of what's needed for the instruction to work. On architectures with register renaming (which is all high-performance architectures) it can be surprisingly expensive. The very least, it forces a dependency on all previous instructions that write that register, and adds another source operand to the instruction. And on most real architectures, this source operand would be required to be present before the instruction itself can start. This is particularly bad for load instructions, if it pushes back when the load can be submitted to cache. This can wipe out all your memory parallelism, and effectively cut your performance to a fraction of what it would othewise be. The basic mental model you need to have is that every instruction that writes to a register always gets a new register that starts with all bits zeroed. To have anything else, you have to do work.
runehol 4y ago
This case is handled correctly. SVE loops don't count up a fixed number of elements per loop iteration, instead they count up the number of elements set in the predicate register. If you perform a page-crossing load where, say, only elements 0-5 out of 32 elements are loaded, then only elements 0-5 in the predicate register gets set, the loop steps 6 elements instead of 32 elements in this iteration. On the next time around, if you really intended to go past the end, byte 0 of the next page will be in the first element position and goes through normal fault handling. Lemire's example loop is subtly wrong here, but the version in the SVE slides he links to is fine.

blake1 4y ago

Always amusing when the assembly language version is so much terser than the C version.

dvhh 4y ago
Isn't that the goal of higher level language to start with ?
- gaganyaan 4y ago
  I think you read their comment backwards? I'd expect the higher level language to be terser in most scenarios.
zamadatix 4y ago
Feels like cheating to say that about a function written in intrinsics though.
sebazzz 4y ago
Yes, but some x64 compilers like Microsoft Visual C++ don't allow raw assembly in C++ (it did allow it for x86-32 though)
- my123 4y ago
  Not allowed for MSVC on arm and arm64 too.
Liquid_Fire 4y ago
To be fair, the assembly version seems to be missing about half the function, so it's not exactly a fair comparison.

Gigachad 4y ago

Why does C not just store the length of the string before the string itself?

vlovich123 4y ago
Probably a historical artifact from when the extra 4-8 bytes required posed a serious overhead. The other advantage is that there’s nothing involved in porting C strings between 8, 16, 32, and 64 bit machines. Of course, most modern languages will store the length separately (using small string optimization) AND offer a way to convert to a C string (for OS interop). There’s an argument that taking a substring off a C string a) can be done without allocating a copy b) can be done with pure pointer manipulation. In practice though I’m not sure how critical that case is.
- cplusplusfellow 4y ago
  This could also be achieved by locating the pointer and the (offset and length) as separate.
  - stevefan1999 4y ago
    This will cause a lot of indirect access which can be a problem in the 70s-80s' because this not only requires more memory but this also requires many more operations (say like LEA) to extract a slice. This might work fine in a bank mainframe, but is prohibitively expensive in the minicomputers back in the days. C is written for Unix. Unix is written with minicomputers in mind. Thus C is somewhat influenced by minicomputers and has to work on their setback in the good ol' days. You have to think in the historic context.
    - masklinn 4y ago
      > This will cause a lot of indirect access It causes strictly less indirect access if you store it as part of the string struct, as C++, Go, or Rust do.

synergy20 4y ago

c++ string has size meta info builtin so you no longer need strlen?