# Count words challenge

**URL:** <https://discourse.julialang.org/t/count-words-challenge/57221>\
**Category:** Performance\
**Created:** [March 15, 2021, 5:52pm UTC](https://discourse.julialang.org/t/count-words-challenge/57221 "2021-03-15T17:52:37Z")\
**Posts on this page:** 20\
**Page:** 1

<div class="post-metadata">

**Author:** ![alemelis](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/alemelis/32/208433_2.png) [@alemelis](https://discourse.julialang.org/u/alemelis)\
**Post date:** [March 15, 2021, 5:52pm UTC](https://discourse.julialang.org/t/count-words-challenge/57221/1 "2021-03-15T17:52:37Z")

</div>

Hello!

I’ve been reading [this blog post](https://benhoyt.com/writings/count-words/) today and decided to give it a try in Julia.

In short, the idea is to benchmark different languages in counting words frequency for long text files.

I’ve [added](https://github.com/benhoyt/countwords/pull/26) what I believe is the “simple” version from the blog, but I’d like to see from more experienced devs what Julia can actually achieve.

Most important, you’re not allowed to use third-party libraries, only the standard one.

---

<div class="post-metadata">

**Author:** ![alemelis](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/alemelis/32/208433_2.png) [@alemelis](https://discourse.julialang.org/u/alemelis)\
**Post date:** [March 15, 2021, 6:04pm UTC](https://discourse.julialang.org/t/count-words-challenge/57221/2 "2021-03-15T18:04:36Z")

</div>

![Screenshot 2021-03-15 at 18.01.04](https://global.discourse-cdn.com/julialang/original/3X/0/8/08c2488d0e45a2792133b63929a6120728c3ff15.png)

profiler view

seems like the algorithm is OK, it’s just split and lowercase to take most of the time

---

<div class="post-metadata">

**Author:** ![rdeits](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/rdeits/32/286_2.png) [@rdeits](https://discourse.julialang.org/u/rdeits)\
**Post date:** [March 15, 2021, 6:05pm UTC](https://discourse.julialang.org/t/count-words-challenge/57221/3 "2021-03-15T18:05:36Z")

</div>

BTW, your code returns 0 for every word because you’re doing `get!(counter, word, 0) + 1` but not actually putting the increased count back into the dict.

---

<div class="post-metadata">

**Author:** ![alemelis](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/alemelis/32/208433_2.png) [@alemelis](https://discourse.julialang.org/u/alemelis)\
**Post date:** [March 15, 2021, 6:09pm UTC](https://discourse.julialang.org/t/count-words-challenge/57221/4 "2021-03-15T18:09:00Z")

</div>

indeed, thanks for spotting it

it should be `counter[word] = get!(counter, word, 0) + 1`

---

<div class="post-metadata">

**Author:** ![rdeits](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/rdeits/32/286_2.png) [@rdeits](https://discourse.julialang.org/u/rdeits)\
**Post date:** [March 15, 2021, 6:11pm UTC](https://discourse.julialang.org/t/count-words-challenge/57221/5 "2021-03-15T18:11:17Z")

</div>

Another small improvement is to concretely type your `Dict`:

Here’s the original code:

```julia
julia> @btime wc(readlines("kjvbible.txt")) |> sortdict
  276.591 ms (3810469 allocations: 177.55 MiB)

```

New code:

```julia
function wc(lines, counter=Dict{String, Int}())
    for line in lines, word in split(line)
    	l = lowercase(word)
    	counter[l] = get(counter, l, 0) + 1
    end
    counter
end

```

```julia
julia> @btime wc(readlines("kjvbible.txt")) |> sortdict
  230.545 ms (2918982 allocations: 163.95 MiB)

```

---

<div class="post-metadata">

**Author:** ![Skoffer](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/skoffer/32/378_2.png) [@Skoffer](https://discourse.julialang.org/u/Skoffer)\
**Post date:** [March 15, 2021, 6:38pm UTC](https://discourse.julialang.org/t/count-words-challenge/57221/6 "2021-03-15T18:38:02Z")

</div>

You should use `eachline` instead of `readlines`. There is no need to put whole text in memory, when you can read it from the input stream.

---

<div class="post-metadata">

**Author:** ![baggepinnen](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/baggepinnen/32/693_2.png) [@baggepinnen](https://discourse.julialang.org/u/baggepinnen)\
**Post date:** [March 15, 2021, 6:40pm UTC](https://discourse.julialang.org/t/count-words-challenge/57221/7 "2021-03-15T18:40:14Z")

</div>

The following avoids doing the hash lookup for the dict twice by retrieving a Ref value and updating that

```julia
function wc(lines, counter=Dict{String, Ref{Int}}())
    for line in lines, word in split(line)
    	l = lowercase(word)
    	c = get(counter, l, Ref{Int}(0))
        c[] += 1
    end
    counter
end

@btime wc(readlines("/home/fredrikb/Downloads/kjvbible.txt"))
# 281.450 ms (2918978 allocations: 162.72 MiB) original
# 228.156 ms (3740085 allocations: 173.83 MiB) Ref 

```

EDIT: See @ericphanson s post below, `get` should be replaced by `get!` for the behaviour to be correct, after which this implementation is not actually faster 😕 Thanks for pointing it out though Eric 🙂

---

<div class="post-metadata">

**Author:** ![yha](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/yha/32/3502_2.png) [@yha](https://discourse.julialang.org/u/yha)\
**Post date:** [March 15, 2021, 6:43pm UTC](https://discourse.julialang.org/t/count-words-challenge/57221/8 "2021-03-15T18:43:10Z")

</div>

> [@alemelis](#):
>
> ```julia
> sortdict(counter) = sort(collect(counter), by=x->x[2], rev=true)
> 
> ```

A minor optimization: use `sort!`, since you’ve already allocated a new array with `collect`.

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [March 15, 2021, 6:46pm UTC](https://discourse.julialang.org/t/count-words-challenge/57221/9 "2021-03-15T18:46:55Z")

</div>

Other possibilities:

You could also implement a `SubString` wrapper type with custom `isequal` and `hash` functions that ignore case (and maybe cache the hash in the `struct`). And you could avoid allocating the array of `split` results by simply looping within the line and creating your substring objects as you go along. And you could avoid allocating strings for the lines by simply mmapping the file and using a [StringView](https://github.com/JuliaStrings/StringViews.jl) of the mmap array or portions thereof, and looping through the bytes looking for whitespace.

i.e. you could cut down on the number of heap allocations enormously if you _really_ cared about optimizing this (in the same way that CSV.jl hugely optimized parsing csv files). (You could even specialize things for ASCII if you know the text is ASCII-only.)

---

<div class="post-metadata">

**Author:** ![ericphanson](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/ericphanson/32/215186_2.png) [@ericphanson](https://discourse.julialang.org/u/ericphanson)\
**Post date:** [March 15, 2021, 6:53pm UTC](https://discourse.julialang.org/t/count-words-challenge/57221/10 "2021-03-15T18:53:37Z")

</div>

I think it should be `get!` instead of `get`

---

<div class="post-metadata">

**Author:** ![alemelis](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/alemelis/32/208433_2.png) [@alemelis](https://discourse.julialang.org/u/alemelis)\
**Post date:** [March 15, 2021, 7:10pm UTC](https://discourse.julialang.org/t/count-words-challenge/57221/11 "2021-03-15T19:10:51Z")

</div>

Lots of nice suggestions thanks!

I think the spirit of the challenge is to first solve the problem in the easiest idiomatic way. The second step is to provide the optimized version which may not be straightforward to implement.

---

<div class="post-metadata">

**Author:** ![Skoffer](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/skoffer/32/378_2.png) [@Skoffer](https://discourse.julialang.org/u/Skoffer)\
**Post date:** [March 15, 2021, 7:33pm UTC](https://discourse.julialang.org/t/count-words-challenge/57221/12 "2021-03-15T19:33:45Z")

</div>

I do not know, this one looks rather idiomatic and simple (sorry, I didn’t use `Ref` trick, it is cool, but more advanced)

```julia
function wc(io, counter=Dict{String, Int}())
    for line in eachline(io)
        for word in split(line)
            word = lowercase(word)
            counter[word] = get!(counter, word, 0) + 1
        end
    end
    counter
end

sortdict(counter) = sort!(collect(counter), by=x->x[2], rev=true)

wc(stdin) |> sortdict .|> kv->println(kv[1], " ", kv[2])

```

These changes reduced time from 1.2s to 0.97 on my laptop, when I am running this command.

```julia
time julia simple.jl < /tmp/kjvbible.txt >> /dev/null

```

P.S.: during Advent of Code someone wrote iterating version of `split`, would be nice to have it somewhere accessible (maybe even stdlib?), then it would be possible to write `for word in Iterators.split(line)` instead of `for word in split(line)`

---

<div class="post-metadata">

**Author:** ![ericphanson](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/ericphanson/32/215186_2.png) [@ericphanson](https://discourse.julialang.org/u/ericphanson)\
**Post date:** [March 15, 2021, 7:56pm UTC](https://discourse.julialang.org/t/count-words-challenge/57221/13 "2021-03-15T19:56:02Z")

</div>

I think it’s a little bit faster if you do `Base.RefValue{Int}` in dictionary type, instead of `Ref{Int}`, since that’s actually not a concrete type.

---

<div class="post-metadata">

**Author:** ![rdeits](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/rdeits/32/286_2.png) [@rdeits](https://discourse.julialang.org/u/rdeits)\
**Post date:** [March 15, 2021, 8:03pm UTC](https://discourse.julialang.org/t/count-words-challenge/57221/14 "2021-03-15T20:03:43Z")

</div>

> [@Skoffer](#):
>
> `counter[word] = get!(counter, word, 0) + 1`

Using `get!` here is unnecessary (and slightly wasteful) because you’re already writing to `counter[word]` on the left-hand side.

With `get!`, this code does (roughly):

```julia
if word in keys(counter)
  x = counter[word]
else
  counter[word] = 0 # this is unnecessary
  x = 0
end
counter[word] = x + 1

```

If you use `get` instead (no `!` ), then the code instead does (roughly):

```julia
if word in keys(counter)
  x = counter[word]
else
  x = 0
end
counter[word] = x + 1

```

Results with `get!`:

```julia
julia> @btime wc(open("kjvbible.txt")) |> sortdict
  245.357 ms (2918965 allocations: 161.94 MiB)

```

and with `get` instead:

```julia
julia> @btime wc(open("kjvbible.txt")) |> sortdict
  239.684 ms (2918965 allocations: 161.94 MiB)

```

Slightly faster, although it may just be noise.

---

<div class="post-metadata">

**Author:** ![baggepinnen](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/baggepinnen/32/693_2.png) [@baggepinnen](https://discourse.julialang.org/u/baggepinnen)\
**Post date:** [March 15, 2021, 8:32pm UTC](https://discourse.julialang.org/t/count-words-challenge/57221/15 "2021-03-15T20:32:02Z")

</div>

You’re right, that does recover some performance, it’s now on par with the version without any Ref ^^

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [March 15, 2021, 9:12pm UTC](https://discourse.julialang.org/t/count-words-challenge/57221/16 "2021-03-15T21:12:58Z")

</div>

In particular, here is one that avoids allocating any strings until the end, by using a custom type for the keys that does a case-insensitive hash in-place on a view of the mmapped file, and specializing for ASCII data. On my machine, `@btime wordcount3("kjvbible.txt")` is 2–3x faster than those above.

```julia
using Mmap

# custom array-like ASCII-case-insensitive bytes-view object
# with fast case-insensitive hash
struct MyStringView{V<:AbstractVector{UInt8}} <: AbstractVector{UInt8}
    data::V
end

lc(byte::UInt8) = UInt8('A') ≤ byte ≤ UInt8('Z') ? byte + (UInt8('a')-UInt8('A')) : byte

Base.size(a::MyStringView) = size(a.data)
Base.@propagate_inbounds Base.getindex(a::MyStringView, i::Int) = lc(a.data[i])

const FNV_prime = UInt(sizeof(UInt) == 8 ? 1099511628211 : 16777619)
const FNV_offset = UInt(sizeof(UInt) == 8 ? 14695981039346656037 : 2166136261)

function Base.hash(a::MyStringView, h::UInt)
    ha = FNV_offset
    @inbounds for i = 1:length(a)
         ha = (ha * FNV_prime) ⊻ a[i] # FNV-1 hash
    end
    return ha ⊻ h
end

iswordbyte(b::UInt8) = (b != UInt8(' ')) & (b != UInt8('\n'))

@views function wc3(io)
    bytes = Mmap.mmap(io)
    words = Dict{MyStringView{typeof(bytes[1:0])},typeof(Ref(0))}()
    sizehint!(words, length(bytes) ÷ 10)
    s = 1
    while true
        s = findnext(iswordbyte, bytes, s)
        isnothing(s) && break
        e = something(findnext(!iswordbyte, bytes, s+1), length(bytes)+1)
        word = MyStringView(bytes[s:e-1])
        c = get!(words, word, Ref(0))
        c[] += 1
        s = e+1
    end
    return sort!([String(k) => v[] for (k,v) in words], by=x->x[2], rev=true)
end
wordcount3(filename) = open(wc3, filename)

```

It could be optimized in further ways. For example, I experimented with implementing a `get!`-like function that increments the dictionary contents in-place (or initializes the count to `1`) without `Ref`, by copying the [`get!` source code from `base/dict.jl`](https://github.com/JuliaLang/julia/blob/8fc52931fca94f4247f2b0e8f69447f8417d70ab/base/dict.jl#L459-L477), but it only gained me an additional 10%. Probably you could gain additional speed for hashing etcetera by examining several bytes at once — you can do lots of optimizations if you know you have ASCII data.

_Update_: simplified the above code by making `MyStringView` a subtype of `AbstractVector`, which cuts down on the number of methods I needed to implement. Also updated to use `findnext` instead of explicit loops, which is shorter while being just as fast.

---

<div class="post-metadata">

**Author:** ![jules](https://avatars.discourse-cdn.com/v4/letter/j/41988e/32.png) [@jules](https://discourse.julialang.org/u/jules)\
**Post date:** [March 15, 2021, 9:15pm UTC](https://discourse.julialang.org/t/count-words-challenge/57221/17 "2021-03-15T21:15:08Z")

</div>

I also just tried ascii optimizations, although it seems the bottleneck is the dict insertions. My idea was that it shouldn’t matter much to apply lowercasing to every string, maybe it’s better to just do that at the end when the number strings is really small.

```julia
using Mmap
function wordcount()
    arr = Mmap.mmap(expanduser("~/Downloads/kjvbible.txt"))
    start = 0
    finish = 0

    within_word = false

    counts = Dict{typeof(view(arr, 1:2)), Int}()

    for (i, byte) in enumerate(arr)
        # A-Z, a-z
        if (0x41 <= byte <= 0x5a) || (0x61 <= byte <= 0x7a)
            if !within_word
                start = i
                within_word = true
            end
        elseif within_word
            finish = i - 1
            within_word = false

            lastword = view(arr, start:finish)
            counts[lastword] = get!(counts, lastword, 0) + 1
        end
    end

    stringcounts = Dict{String, Int}()
    for (key, value) in counts
        lckey = lowercase(String(key))
        stringcounts[lckey] = get!(stringcounts, lckey, 0) + value
    end

    sort!(collect(stringcounts), by = last, rev = true)
end

@time wordcount()

0.237530 seconds (67.86 k allocations: 8.770 MiB)

```

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [March 15, 2021, 9:17pm UTC](https://discourse.julialang.org/t/count-words-challenge/57221/18 "2021-03-15T21:17:03Z")

</div>

> [@jules](#):
>
> I also just tried ascii optimizations, although it seems the bottleneck is the dict insertions:

Your code is 4x slower than mine (above), and also seems to have a bug — it gives a different result than the other programs.

---

<div class="post-metadata">

**Author:** ![jules](https://avatars.discourse-cdn.com/v4/letter/j/41988e/32.png) [@jules](https://discourse.julialang.org/u/jules)\
**Post date:** [March 15, 2021, 9:21pm UTC](https://discourse.julialang.org/t/count-words-challenge/57221/19 "2021-03-15T21:21:36Z")

</div>

Yeah makes sense, the custom hashing can save a lot. No idea where the bug is, but also no more motivation to check 🙂

---

<div class="post-metadata">

**Author:** ![ericphanson](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/ericphanson/32/215186_2.png) [@ericphanson](https://discourse.julialang.org/u/ericphanson)\
**Post date:** [March 15, 2021, 9:45pm UTC](https://discourse.julialang.org/t/count-words-challenge/57221/20 "2021-03-15T21:45:20Z")

</div>

I tried using Automata.jl along with your custom string type, and it benchmarked basically exactly the same as your code when I used a view, but without a view it was almost twice as slow as your code. Adding a view to your code doesn’t seem to change the timings there for me though. (I know using packages is against the rules of the blog post, I just wanted to try it out).

```julia
# needs the code in https://discourse.julialang.org/t/count-words-challenge/57221/17 to be run first
using Automa, BenchmarkTools, Mmap
using Automa.RegExp: space, neg, opt, rep

word = neg(space())
doc = opt(word) * rep(space() * word) * space()

word.actions[:exit] = [:exit_word]
word.actions[:enter] = [:enter_word]

machine = Automa.compile(doc)

actions = Dict(:enter_word => quote
                    mark = p
                end,
                :exit_word => quote
                    c = get!(counter, MyStringView(@view data[mark:p-1]), Ref{Int}(0))
                    c[] += 1
            end)

# Generate a function using @eval.
context = Automa.CodeGenContext()

@eval function wordcount4(filename)
    data = Mmap.mmap(filename)
    counter = Dict{MyStringView{typeof(@view data[2:3])},typeof(Ref(0))}()

    mark = 0

    # generate code to initialize variables used by FSM
    $(Automa.generate_init_code(context, machine))

    # set end and EOF positions of data buffer
    p_end = p_eof = lastindex(data)

    # generate code to execute FSM
    $(Automa.generate_exec_code(context, machine, actions))

    # check if FSM properly finished
    if cs != 0
        error("failed to count words on byte $p")
    end

    # assemble the result with SGJ's code
    return sort!([String(k) => v[] for (k,v) in counter], by=x->(x[2],x[1]), rev=true)
end

@btime wordcount4("input.txt")

```

[Next page](https://discourse.julialang.org/t/count-words-challenge/57221.md?page=2)