DEV Community: Taras Tsugrii

EIP-55: Mixed-case checksum address encoding.

Taras Tsugrii — Sat, 24 Apr 2021 21:32:52 +0000

Mistakes can get fairly expensive when it comes to dealing with money. Because of this, Bitcoin implemented error detection using checksums to catch attempts to use invalid addresses. Ethereum decided to take more compositional approach and delegate this functionality to higher-level systems, but while they are being created and adopted many users are losing their money. Implementing checksum is fairly easy, but the tricky part is doing it in a backwards compatible way. Take a minute and try to come up with a way to add checksums to Ethereum addresses without changing them. Hint:

Ethereum Addresses are based on the Hexadecimal format (also base16 or hex). [...]. Ethereum addresses are not case sensitive and can be used as lowercase or uppercase.
Since addresses are case insensitive, what if we use casing to embed checksum information? That's exactly what Vitalik proposed in EIP-55:

def checksum_encode(addr): # Takes a 20-byte binary address as input
    hex_addr = addr.hex()
    checksummed_buffer = ""

    # Treat the hex address as ascii/utf-8 for keccak256 hashing
    hashed_address = eth_utils.keccak(text=hex_addr).hex()

    # Iterate over each character in the hex address
    for nibble_index, character in enumerate(hex_addr):

        if character in "0123456789":
            # We can't upper-case the decimal digits
            checksummed_buffer += character
        elif character in "abcdef":
            # Check if the corresponding hex digit (nibble) in the hash is 8 or higher
            hashed_address_nibble = int(hashed_address[nibble_index], 16)
            if hashed_address_nibble > 7:
                checksummed_buffer += character.upper()
            else:
                checksummed_buffer += character
        else:
            raise eth_utils.ValidationError(
                f"Unrecognized hex character {character!r} at position {nibble_index}"
            )

    return "0x" + checksummed_buffer

Basically we are computing a checksum using keccak256 and use its hex representation as a mask to decide whether hex digit of the address should be upper-cased based on a value of the checksum at the same position:

...
            # Check if the corresponding hex digit (nibble) in the hash is 8 or higher
            hashed_address_nibble = int(hashed_address[nibble_index], 16)
            if hashed_address_nibble > 7:
                checksummed_buffer += character.upper()
            else:
                checksummed_buffer += character
...

Older clients ignore the case and don't perform the check, hence backwards compatibility, but newer clients perform the check and detect errors.
It's fascinating that such a simple, cheap and backwards compatible technique

On average there will be 15 check bits per address, and the net probability that a randomly generated address if mistyped will accidentally pass a check is 0.0247%. This is a ~50x improvement over ICAP, but not as good as a 4-byte check code.

This underscores the value of specification, since it defines behavior, and is a great example of clever way to embed additional information.

Trading memory for fewer allocations.

Taras Tsugrii — Sat, 24 Apr 2021 21:30:10 +0000

Even though memory allocations are not always easy to spot, they are fairly expensive due to overhead and garbage collector load. In a seemingly innocent function print_int

func print_int(x int) {
    fmt.Println(x)
}

compiler claims (-gcflags="-m")

x escapes to heap

so runtime.convT64 function is used to convert x into a pointer

00007 (6) CALL runtime.convT64(SB)

which is implemented in runtime.iface.go:

func convT64(val uint64) (x unsafe.Pointer) {
    if val < uint64(len(staticuint64s)) {
        x = unsafe.Pointer(&staticuint64s[val])
    } else {
        x = mallocgc(8, uint64Type, false)
        *(*uint64)(x) = val
    }
    return
}

The most interesting bit is x = unsafe.Pointer(&staticuint64s[val]) part, which returns a pointer from a preallocated staticuint64s pool of ints between 0 and 255:

// staticuint64s is used to avoid allocating in convTx for small integer values.
var staticuint64s = [...]uint64{
    0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
    0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f,
    ...
    0xf8, 0xf9, 0xfa, 0xfb, 0xfc, 0xfd, 0xfe, 0xff,
}

It's a fairly cheap way to trade a little memory for allocation reduction and is used in many other managed languages like Java. To make it even more useful, runtime reuses the same cache also for convT16 and convT32 functions.

It's such a useful technique that it's also used for dynamic caches, also known as object pools, but the extra flexibility of not being limited by a fairly small range of values comes at a cost of synchronization, so it's important to measure this overhead when evaluating object pools.

In summary, consider using static preallocated caches to reduce allocation count and improve performance.

Don't leave easy performance wins on the table.

Taras Tsugrii — Sat, 24 Apr 2021 21:26:53 +0000

One of the most exciting feature of Java 16 is vector API (JEP 338) that makes it possible to take advantage of available SIMD instructions and by doing so significantly improve performance.

When reading an example from JEP documentation I was somewhat shocked to see that a simple scalar computation

void scalarComputation(float[] a, float[] b, float[] c) {
  for (int i = 0; i < a.length; i++) {
    c[i] = (a[i] * a[i] + b[i] * b[i]) * -1.0f;
  }
}

has to be rewritten as a hardly readable

static final VectorSpecies<Float> SPECIES = FloatVector.SPECIES_PREFERRED;

void vectorComputation(float[] a, float[] b, float[] c,
        VectorSpecies<Float> species) {
    int i = 0;
    int upperBound = species.loopBound(a.length);
    for (; i < upperBound; i += species.length()) {
        //FloatVector va, vb, vc;
        var va = FloatVector.fromArray(species, a, i);
        var vb = FloatVector.fromArray(species, b, i);
        var vc = va.mul(va).
                    add(vb.mul(vb)).
                    neg();
        vc.intoArray(c, i);
    }

    for (; i < a.length; i++) {
        c[i] = (a[i] * a[i] + b[i] * b[i]) * -1.0f;
    }
}

vectorComputation(a, b, c, SPECIES);

to get the desired vectorized assembly.

  0.43%  / │  0x0000000113d43890: vmovdqu 0x10(%r8,%rbx,4),%ymm0
  7.38%  │ │  0x0000000113d43897: vmovdqu 0x10(%r10,%rbx,4),%ymm1
  8.70%  │ │  0x0000000113d4389e: vmulps %ymm0,%ymm0,%ymm0
  5.60%  │ │  0x0000000113d438a2: vmulps %ymm1,%ymm1,%ymm1
 13.16%  │ │  0x0000000113d438a6: vaddps %ymm0,%ymm1,%ymm0
 21.86%  │ │  0x0000000113d438aa: vxorps -0x7ad76b2(%rip),%ymm0,%ymm0
  7.66%  │ │  0x0000000113d438b2: vmovdqu %ymm0,0x10(%r9,%rbx,4)
 26.20%  │ │  0x0000000113d438b9: add    $0x8,%ebx
  6.44%  │ │  0x0000000113d438bc: cmp    %r11d,%ebx
         \ │  0x0000000113d438bf: jl     0x0000000113d43890

"Phew, great that I don't use Java", thought I and went on to see what would Go do in such case. To my big disappointment, Go does not seem to support SIMD intrinsics and generates non-vectorized assembly :(

Convinced that Clang would not disappoint me I checked the assembly using compiler explorer with highest level of optimization and noticed that even though it does a lot of useful optimizations, including loop unrolling, it's still using only 128bit XMM registers:

...
.LBB0_6: # =>This Inner Loop Header: Depth=1
movups xmm1, xmmword ptr [rsi + 4*rax]
movups xmm2, xmmword ptr [rsi + 4*rax + 16]
mulps xmm1, xmm1
mulps xmm2, xmm2
movups xmm3, xmmword ptr [rdx + 4*rax]
movups xmm4, xmmword ptr [rdx + 4*rax + 16]
mulps xmm3, xmm3
addps xmm3, xmm1
mulps xmm4, xmm4
addps xmm4, xmm2
xorps xmm3, xmm0
xorps xmm4, xmm0
movups xmmword ptr [rcx + 4*rax], xmm3
movups xmmword ptr [rcx + 4*rax + 16], xmm4
add rax, 8
cmp rdi, rax
jne .LBB0_6
cmp rdi, r8
je .LBB0_13
...

but easily switches to 512bit ZMM registers when foundation AVX 512 support is requested via -mavx512f flag:

...
.LBB0_8: # =>This Inner Loop Header: Depth=1
vmovups zmm1, zmmword ptr [rsi + 4*rdi]
vmovups zmm2, zmmword ptr [rsi + 4*rdi + 64]
vmovups zmm3, zmmword ptr [rsi + 4*rdi + 128]
vmovups zmm4, zmmword ptr [rsi + 4*rdi + 192]
vmulps zmm1, zmm1, zmm1
vmulps zmm2, zmm2, zmm2
vmulps zmm3, zmm3, zmm3
vmulps zmm4, zmm4, zmm4
vmovups zmm5, zmmword ptr [rdx + 4*rdi]
vmovups zmm6, zmmword ptr [rdx + 4*rdi + 64]
vmovups zmm7, zmmword ptr [rdx + 4*rdi + 128]
vmovups zmm8, zmmword ptr [rdx + 4*rdi + 192]
vmulps zmm5, zmm5, zmm5
vaddps zmm1, zmm1, zmm5
vmulps zmm5, zmm6, zmm6
vaddps zmm2, zmm2, zmm5
vmulps zmm5, zmm7, zmm7
vaddps zmm3, zmm3, zmm5
vmulps zmm5, zmm8, zmm8
vaddps zmm4, zmm4, zmm5
vpxord zmm1, zmm1, zmm0
vpxord zmm2, zmm2, zmm0
vpxord zmm3, zmm3, zmm0
vpxord zmm4, zmm4, zmm0
vmovdqu64 zmmword ptr [rcx + 4*rdi], zmm1
vmovdqu64 zmmword ptr [rcx + 4*rdi + 64], zmm2
vmovdqu64 zmmword ptr [rcx + 4*rdi + 128], zmm3
vmovdqu64 zmmword ptr [rcx + 4*rdi + 192], zmm4
add rdi, 64
cmp rax, rdi
jne .LBB0_8
cmp rax, r8
je .LBB0_19
test r8b, 56
je .LBB0_14
...

AVX 512 support was added by Intel with the Haswell processor, which shipped in 2013, so it's very likely that in 2021 your servers have it.

Moral of the story?

Don't leave performance on the table - know your hardware and how to take full advantage of it.

Trust performance advice... but verify.

Taras Tsugrii — Sat, 24 Apr 2021 21:24:14 +0000

Just like most things, performance advice also has an expiration date and it's important to keep this in mind when applying suggestions from blog posts or StackOverflow. That's why my favorite command line flag when building Go apps is --gcflags="-m=2". It enables printing optimizer decisions, making it possible to answer numerous interesting questions affecting performance, including whether function is inlined:

cannot inline main: function too complex: cost 523 exceeds budget 80
...
inlining call to largeReturner func() Large { return Large literal }

or whether variable escapes to heap:

main.go:10:2: i escapes to heap:
main.go:10:2:  flow: ~r0 = &i:
main.go:10:2:    from &i (address-of) at main.go:11:9
main.go:10:2:    from return &i (return) at main.go:11:2
main.go:10:2: moved to heap: i

Bonus: do you think l will escape to heap in the following code?

24 type Large struct {
25        data [1024]byte
26 }
27
28 func main() {
29        l := Large{}
30        fmt.Println(l)
...

If you guessed yes, you are right :)

main.go:30:13: l escapes to heap:
main.go:30:13:  flow: ~arg0 = &{storage for l}:
main.go:30:13:    from l (spill) at main.go:30:13
main.go:30:13:    from ~arg0 = <N> (assign-pair) at main.go:30:13
main.go:30:13:  flow: {storage for []interface {} literal} = ~arg0:
main.go:30:13:    from []interface {} literal (slice-literal-element) at main.go:30:13
main.go:30:13:  flow: fmt.a = &{storage for []interface {} literal}:
main.go:30:13:    from []interface {} literal (spill) at ./main.go:30:13
main.go:30:13:    from fmt.a = []interface {} literal (assign) at main.go:30:13
main.go:30:13:  flow: {heap} = *fmt.a:
main.go:30:13:    from fmt.Fprintln(io.Writer(os.Stdout), fmt.a...) (call parameter) at main.go:30:13
main.go:30:13: l escapes to heap

Why it matters? Even if the additional memory indirection is not a problem, heap allocations result in extra work for garbage collector and dreaded stop-the-world pauses.

Moral of the story? Know your tools and use them to verify all performance assumptions.