# How to count all unique character frequency in a string?

**URL:** <https://discourse.julialang.org/t/how-to-count-all-unique-character-frequency-in-a-string/19342>\
**Category:** New to Julia\
**Tags:** question, statistics, strings\
**Created:** [January 7, 2019, 5:05am UTC](https://discourse.julialang.org/t/how-to-count-all-unique-character-frequency-in-a-string/19342 "2019-01-07T05:05:22Z")\
**Posts on this page:** 6\
**Page:** 2

<div class="post-metadata">

**Author:** ![StefanKarpinski](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stefankarpinski/32/24_2.png) [@StefanKarpinski](https://discourse.julialang.org/u/StefanKarpinski)\
**Post date:** [January 7, 2019, 6:33pm UTC](https://discourse.julialang.org/t/how-to-count-all-unique-character-frequency-in-a-string/19342/21 "2019-01-07T18:33:49Z")

</div>

I feel like there’s a joke about different programming language communities in here…

- C: gets a fast simple code that ignores the existence of Unicode
- C++: gets a fast solution that handles Unicode but uses STL and takes five minutes to compile
- Haskell: a clever usage of the S, K and I combinators solves this problem quite elegantly
- Python: everyone agrees that there one correct way to do it, but five ways are proposed and no one can decide which one is correct and Guido is tired of deciding what the one correct way to do things is
- Rust: gets an essay on borrow semantics and mutation
- Julia: gets twelve different ways to do it, including several that are faster than anyone actually needs to count letters, making use of SIMD, threads and farming out work to the nearest top five supercomputer

---

<div class="post-metadata">

**Author:** ![xiaodai](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/xiaodai/32/15937_2.png) [@xiaodai](https://discourse.julialang.org/u/xiaodai)\
**Post date:** [January 7, 2019, 6:59pm UTC](https://discourse.julialang.org/t/how-to-count-all-unique-character-frequency-in-a-string/19342/22 "2019-01-07T18:59:43Z")

</div>

> [@bennedich](#):
>
> or a radix sort depending on the input data

I am pretty proud of this as it’s one of my first open source contributions

---

<div class="post-metadata">

**Author:** ![kristoffer.carlsson](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/kristoffer.carlsson/32/22_2.png) [@kristoffer.carlsson](https://discourse.julialang.org/u/kristoffer.carlsson)\
**Post date:** [January 7, 2019, 7:52pm UTC](https://discourse.julialang.org/t/how-to-count-all-unique-character-frequency-in-a-string/19342/23 "2019-01-07T19:52:18Z")

</div>

> [@DNF](#):
>
> I suggest using SIMD:

Doesn’t look like that code generate any SIMD instructions?

---

<div class="post-metadata">

**Author:** ![DNF](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dnf/32/10191_2.png) [@DNF](https://discourse.julialang.org/u/DNF)\
**Post date:** [January 7, 2019, 8:33pm UTC](https://discourse.julialang.org/t/how-to-count-all-unique-character-frequency-in-a-string/19342/24 "2019-01-07T20:33:04Z")

</div>

Hm. That’s odd. There is a definite speedup, though less than expected.

I amend my advice: use `@simd` 😉

---

<div class="post-metadata">

**Author:** ![xiaodai](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/xiaodai/32/15937_2.png) [@xiaodai](https://discourse.julialang.org/u/xiaodai)\
**Post date:** [January 7, 2019, 11:19pm UTC](https://discourse.julialang.org/t/how-to-count-all-unique-character-frequency-in-a-string/19342/25 "2019-01-07T23:19:38Z")

</div>

I am curious too. Wonder why?

---

<div class="post-metadata">

**Author:** ![bennedich](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/bennedich/32/4894_2.png) [@bennedich](https://discourse.julialang.org/u/bennedich)\
**Post date:** [January 8, 2019, 12:50am UTC](https://discourse.julialang.org/t/how-to-count-all-unique-character-frequency-in-a-string/19342/26 "2019-01-08T00:50:54Z")

</div>

> [@DNF](#):
>
> I suggest using SIMD

Good suggestion! I didn’t see any SIMD instructions either when I tested earlier, but you’re right it’s considerably faster. Looking at the native code, `@simd` simply results in a tighter inner loop.

We can optimize it a bit further by converting the code units to an array, and keeping two separate `count` arrays, which avoids some of the memory dependencies and resulting latency:

```julia
function count_limited_range_multi_count(s)
    cnt1 = zeros(Int, 128)
    cnt2 = zeros(Int, 128)
    sv = unsafe_wrap(Array, pointer(s), sizeof(s))
    @inbounds @simd for n = 1:2:length(sv)
        a = sv[n]
        b = sv[n+1]
        cnt1[a] += 1
        cnt2[b] += 1
    end
    cnt1 .+ cnt2
end

julia> @btime count_limited_range_simd($s);
  59.156 μs (1 allocation: 1.14 KiB)

julia> @btime count_limited_range_multi_count($s);
  44.826 μs (4 allocations: 3.50 KiB)

```

As for SIMD: with AVX512 one could use gather and scatter to read and write 16 counters at a time, but there’s a problem: If there are duplicate characters within the block, the update will not be correct ([explained in more detail here](https://stackoverflow.com/questions/39913707/how-do-the-conflict-detection-instructions-make-it-easier-to-vectorize-loops)).

Instead, I made an attempt using `vload` to load 32 characters at a time (suitable for AVX2), with the hope that updating each count would be done in only 2 instructions:

```s
vpextrb	esi, xmm0, 0
add	qword ptr [rdx + 8*rsi - 8], 1

```

For up to 3 additions, this optimal assembly is generated, but when I unroll the loop with more additions (need 32), it starts generating nonsense assembly. The code is below if anyone knows how this can be done. It works as it is, just not as fast as it could be:

```julia
macro unrolled_add(n)
    esc(Expr(:block, (k -> :( counts[v[$k]] += 1 )).(1:n)...))
end

function count_limited_range_real_simd(s)
    counts = zeros(Int, 128)
    sv = unsafe_wrap(Array, pointer(s), sizeof(s))
    @inbounds @simd for n = 1:32:length(sv)
        v = vload(Vec{32,UInt8}, sv, n)
        @unrolled_add(32) # n <= 3 generates ideal assembly
    end
    counts
end

```

> [@kristoffer.carlsson](#):
>
> You would do it something like this: `struct FastHashChar`

Nice! I would be even more impressed if `Char` and `FastHashChar` could be made to use the same memory (like union in C), so that we wouldn’t have to rebuild the dictionary at the end. For an alphabet this small, it’s cheap of course, but I think that could be useful in other situations.

> [@stevengj](#):
>
> While it is always a fun exercise to try and optimize the heck out of some little problem like this, 99.9% it is not worth it

Agreed… On the other hand most things I learned about Julia came from reading and answering questions like this on this forum. So if not for OP, it is at least worth it to me 🙂

[Previous page](https://discourse.julialang.org/t/how-to-count-all-unique-character-frequency-in-a-string/19342.md?page=1)
