# Fast String processing in Julia vs. Python

**URL:** <https://discourse.julialang.org/t/fast-string-processing-in-julia-vs-python/2443>\
**Category:** General Usage\
**Created:** [March 4, 2017, 3:24pm UTC](https://discourse.julialang.org/t/fast-string-processing-in-julia-vs-python/2443 "2017-03-04T15:24:02Z")\
**Posts on this page:** 19\
**Page:** 2

<div class="post-metadata">

**Author:** ![dpsanders](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dpsanders/32/3573_2.png) [@dpsanders](https://discourse.julialang.org/u/dpsanders)\
**Post date:** [March 4, 2017, 6:48pm UTC](https://discourse.julialang.org/t/fast-string-processing-in-julia-vs-python/2443/21 "2017-03-04T18:48:44Z")

</div>

You are of course completely correct. Embarrassing that I didn’t notice the first error that we always tell people to avoid!!

Try wrapping everything in a function .

---

<div class="post-metadata">

**Author:** ![mbeltagy](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mbeltagy/32/130_2.png) [@mbeltagy](https://discourse.julialang.org/u/mbeltagy)\
**Post date:** [March 4, 2017, 7:18pm UTC](https://discourse.julialang.org/t/fast-string-processing-in-julia-vs-python/2443/22 "2017-03-04T19:18:55Z")

</div>

Thanks @dpsanders and @bkamins

So this the latest version I have so far

```julia
using Combinatorics

"counts the number of occurances of l in s "
count_o(s,l)=count(x->x==l,s)
"The set of ways of concatenating one item from collection A with one from B."
cross(A, B)=["$a$b" for a in A for b in B]
"All combinations of n items; each combo as a concatenated str."
function combos(items, n)
    (join(combo," ") for combo in combinations(items,n))
end

"""The probability of an event, given a sample space of equiprobable outcomes.
event can be either a set of outcomes, or a predicate (true for outcomes in the event)."""
function P(event, space)
    length(intersect(event,space))//length(space)
end

function P(event::Function, space)
    count(event,space)//length(space)
end

suits = "SHDC"
ranks = "A23456789TJQK"
deck = cross(ranks, suits)
Hands = combos(deck, 5) #A massive list of all possible hands
 
function flush(hand)
    s::String=suits
    any(count_o(hand,suit) == 5 for suit in s)
end

P(flush, Hands) #Warm up

```

Total execution time for Julia is now down to `3.94` vs python at `4.36`. This is pretty decent and it also makes for nicer code. The use of generators and avoiding set operators really made a big difference.

However, I am still not fully satisfied. I am still surprised the python did better when full sets and set operators were used.  
Can I infer form that the python’s handling of sets must be better that Julia’s at this stage?

---

<div class="post-metadata">

**Author:** ![mbeltagy](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mbeltagy/32/130_2.png) [@mbeltagy](https://discourse.julialang.org/u/mbeltagy)\
**Post date:** [March 4, 2017, 7:30pm UTC](https://discourse.julialang.org/t/fast-string-processing-in-julia-vs-python/2443/23 "2017-03-04T19:30:14Z")

</div>

For the sake of completeness, the implementation using sets is

```julia
using Combinatorics

"counts the number of occurances of l in s "
count_o(s,l)=count(x->x==l,s)
"The set of ways of concatenating one item from collection A with one from B."
cross(A, B)=["$a$b" for a in A for b in B]
"All combinations of n items; each combo as a concatenated str."
function combos(items, n)
    Set(join(combo," ") for combo in combinations(items,n))
end

"""The probability of an event, given a sample space of equiprobable outcomes.
event can be either a set of outcomes, or a predicate (true for outcomes in the event)."""
function P(event, space)
    event_ = such_that(event, space)
    length(intersect(event_,space))//length(space)
end

#Making use of Julia's multiple dispatch
"The subset of elements in the collection for which the predicate is true."
function such_that(predicate::Function, collection)
    filter(predicate,collection)
end;
"Default return for a collection"
function such_that(event, collection)
    event
end

suits = "SHDC"
ranks = "A23456789TJQK"
deck = cross(ranks, suits)
Hands = combos(deck, 5) #A massive list of all possible hands

function flush(hand)
    s::String=suits
    any(count_o(hand,suit) == 5 for suit in s)
end

P(flush, Hands) #Warm up

```

This takes `14.1` seconds.

---

<div class="post-metadata">

**Author:** ![mbeltagy](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mbeltagy/32/130_2.png) [@mbeltagy](https://discourse.julialang.org/u/mbeltagy)\
**Post date:** [March 5, 2017, 4:51pm UTC](https://discourse.julialang.org/t/fast-string-processing-in-julia-vs-python/2443/24 "2017-03-05T16:51:22Z")

</div>

I continued with more experiments where I tried to preserve use of Sets so as not to deviate from the python code.

In the first variation, I used `collect` instead of simply passing the generator to the `Set` constructor.

```julia
function combos(items, n)
    Set(collect(join(combo," ") for combo = combinations(items,n)))
end

```

The speed improved and execution time went down to `8.7` seconds.

Then I did another variation when I mapped to a preallocated array.

```julia
function combos(items, n)
    combs=combinations(items,n)
    res=Vector{String}(length(combs))
    Set(map!(x->join(x," "),res,collect(combs)))
end

```

Speed improved further to `6.1` seconds.

Conclusions:

1. Constructing a set is always faster when a preallocated array is provided
2. `map!` always works faster than `collect`
3. There is probably room for improving `Set` construction with a generator input.

---

<div class="post-metadata">

**Author:** ![traktofon](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/traktofon/32/591_2.png) [@traktofon](https://discourse.julialang.org/u/traktofon)\
**Post date:** [March 6, 2017, 6:24am UTC](https://discourse.julialang.org/t/fast-string-processing-in-julia-vs-python/2443/25 "2017-03-06T06:24:01Z")

</div>

On the risk of getting off topic, I would like to encourage a non-string solution for this problem. I see two problems with the string approach:

1. The current implementation relies on the fact that the characters in `suits` and `ranks` don’t overlap, which is just a fortuitousness in the English language.
2. In Python, using strings is probably more performant than using an abstraction, because operations on builtin types are much faster than on user-defined types.

But in Julia we can have abstractions at zero cost, which can also make the code safer. In this spirit I would like to offer the following version:

```julia
using Combinatorics

const suits = "SHDC"
const ranks = "A23456789TJQK"
 
immutable Card{TS,TR}
   suit :: TS
   rank :: TR
end

"""The probability of an event, given a sample space of equiprobable outcomes.
event can be either a set of outcomes, or a predicate (true for outcomes in the event)."""
function P(event::Function, space)
    count(event,space)//length(space)
end

function flush(hand)
    any( count(card -> card.suit==s, hand) == 5 for s in suits )
end

function main()
    deck = [Card(s,r) for r in ranks for s in suits]
    hands = combinations(deck, 5) 
    P(flush, hands) #Warm up
    @time p = P(flush, hands)
    println(p)
end

main()

```

With julia 0.5.0, this gets me:

```julia
  0.624516 seconds (20.79 M allocations: 991.425 MB, 9.39% gc time)

```

The main speedup comes from not using strings, but using the dedicated `Card` type, and having a hand simply be a list of `Card`s (thus avoiding the strings). The other changes I made (explicitly marking global variables as const, and putting the top-level code into a `main` function) have little impact on the speed. A little more speed can actually be gained by changing the defintion of `suits` as follows:

```julia
@enum SUIT spades hearts diamonds clubs
const suits = instances(SUIT)

```

which gets me

```julia
  0.531291 seconds (20.79 M allocations: 991.425 MB, 10.73% gc time)

```

(I guess on current architectures, `Char`s are too small so that operating on them individually incurs too much overhead.)

Note: on my machine the original Python version takes 5.4 seconds.

---

<div class="post-metadata">

**Author:** ![dpsanders](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dpsanders/32/3573_2.png) [@dpsanders](https://discourse.julialang.org/u/dpsanders)\
**Post date:** [March 6, 2017, 6:28am UTC](https://discourse.julialang.org/t/fast-string-processing-in-julia-vs-python/2443/26 "2017-03-06T06:28:50Z")

</div>

Very nice!

---

<div class="post-metadata">

**Author:** ![dpsanders](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dpsanders/32/3573_2.png) [@dpsanders](https://discourse.julialang.org/u/dpsanders)\
**Post date:** [March 6, 2017, 6:32am UTC](https://discourse.julialang.org/t/fast-string-processing-in-julia-vs-python/2443/27 "2017-03-06T06:32:02Z")

</div>

Probably some more speed can be gained (also in the original version) by replacing the `flush` function to just check if all the suits are equal to each other.

---

<div class="post-metadata">

**Author:** ![traktofon](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/traktofon/32/591_2.png) [@traktofon](https://discourse.julialang.org/u/traktofon)\
**Post date:** [March 6, 2017, 6:36am UTC](https://discourse.julialang.org/t/fast-string-processing-in-julia-vs-python/2443/28 "2017-03-06T06:36:45Z")

</div>

@dpsanders is right, in my version replacing `flush` by

```julia
function flush(hand)
    s1 = hand[1].suit
    count(card -> card.suit==s1, hand) == 5
end

```

yields

```julia
  0.388377 seconds (15.59 M allocations: 872.454 MB, 11.35% gc time)

```

i.e. another ~25% faster.

---

<div class="post-metadata">

**Author:** ![dpsanders](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dpsanders/32/3573_2.png) [@dpsanders](https://discourse.julialang.org/u/dpsanders)\
**Post date:** [March 6, 2017, 6:38am UTC](https://discourse.julialang.org/t/fast-string-processing-in-julia-vs-python/2443/29 "2017-03-06T06:38:41Z")

</div>

Instead of an enum, you can just use integers instead of `Char`s for suits and ranks, and get a similar speedup. I am curious as to why there’s still so much allocation.

---

<div class="post-metadata">

**Author:** ![dpsanders](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dpsanders/32/3573_2.png) [@dpsanders](https://discourse.julialang.org/u/dpsanders)\
**Post date:** [March 6, 2017, 6:42am UTC](https://discourse.julialang.org/t/fast-string-processing-in-julia-vs-python/2443/30 "2017-03-06T06:42:03Z")

</div>

> [@traktofon](#):
>
> function flush(hand)  
> s1 = hand[1].suit  
> count(card -\> card.suit==s1, hand) == 5  
> end

Or just

```julia
function flush(hand)
    hand[1].suit == hand[2].suit == hand[3].suit == hand[4].suit == hand[5].suit
end

```

which is even slightly faster. Not sure how to write this more beautifully.

---

<div class="post-metadata">

**Author:** ![dpsanders](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dpsanders/32/3573_2.png) [@dpsanders](https://discourse.julialang.org/u/dpsanders)\
**Post date:** [March 6, 2017, 6:42am UTC](https://discourse.julialang.org/t/fast-string-processing-in-julia-vs-python/2443/31 "2017-03-06T06:42:54Z")

</div>

`all(card.suit==s1 for card in hand)`

---

<div class="post-metadata">

**Author:** ![dpsanders](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dpsanders/32/3573_2.png) [@dpsanders](https://discourse.julialang.org/u/dpsanders)\
**Post date:** [March 6, 2017, 7:00am UTC](https://discourse.julialang.org/t/fast-string-processing-in-julia-vs-python/2443/32 "2017-03-06T07:00:09Z")

</div>

Ah, the allocations come from traversing the generator of the combinations.

---

<div class="post-metadata">

**Author:** ![dpsanders](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dpsanders/32/3573_2.png) [@dpsanders](https://discourse.julialang.org/u/dpsanders)\
**Post date:** [March 6, 2017, 7:04am UTC](https://discourse.julialang.org/t/fast-string-processing-in-julia-vs-python/2443/33 "2017-03-06T07:04:15Z")

</div>

Indeed, if you actually do `hands = collect(combinations(deck, 5))`, then the allocations go down to 0, and the goes down to 0.05 secs!

---

<div class="post-metadata">

**Author:** ![traktofon](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/traktofon/32/591_2.png) [@traktofon](https://discourse.julialang.org/u/traktofon)\
**Post date:** [March 6, 2017, 7:13am UTC](https://discourse.julialang.org/t/fast-string-processing-in-julia-vs-python/2443/34 "2017-03-06T07:13:43Z")

</div>

But that moves much of the work from the `P` function into the `collect` operation, so to be fair we should time that as well. Rewriting the bottom part to

```julia
function main()
    deck = [Card(s,r) for r in ranks for s in suits]
    hands = combinations(deck, 5)
    p = P(flush, hands)
    println(p)
end

@time main() # Warm up
@time main()

```

gives me

```julia
  0.905246 seconds (18.43 M allocations: 961.952 MB, 27.77% gc time)
  0.419223 seconds (18.19 M allocations: 951.772 MB, 14.00% gc time)

```

but adding the `collect` call for the combinations gives me

```julia
  1.461934 seconds (18.45 M allocations: 982.869 MB, 31.46% gc time)
  1.061860 seconds (18.19 M allocations: 971.600 MB, 32.99% gc time)

```

---

<div class="post-metadata">

**Author:** ![ChrisRackauckas](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/chrisrackauckas/32/77_2.png) [@ChrisRackauckas](https://discourse.julialang.org/u/ChrisRackauckas)\
**Post date:** [March 6, 2017, 3:53pm UTC](https://discourse.julialang.org/t/fast-string-processing-in-julia-vs-python/2443/35 "2017-03-06T15:53:01Z")

</div>

Another way to speed up string processing code which I don’t think has been mentioned here is to use a different type of string. Julia defaults to UTF8, which is a variable length encoding and can slow some calculations down. You may want to look at LegacyStrings.jl or some of the stuff in [JuliaString](https://github.com/JuliaString) if you need even more speed.

---

<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:** [March 7, 2017, 5:11am UTC](https://discourse.julialang.org/t/fast-string-processing-in-julia-vs-python/2443/36 "2017-03-07T05:11:56Z")

</div>

It’s unclear (to me at least) which version of Julia you’re using here, @mbeltagy, so I should mention that strings on 0.6-alpha should be _much_ faster than they were on 0.5. They have, until 0.6 been slower than Python, but should now be the same (or hopefully even faster). In the future, we have a few potential tricks that could make them even faster still, but they’re fairly tricky tricks, so it’s hard to say for sure. Of course, we want all aspects of Julia to be at least as fast any other language, but we haven’t quite gotten to that state of performance nirvana yet. Strings are something Python has been very good at for a long time (and Perl is even better); now at least Julia should be competitive.

I should also mention that although we surely can and will, we often haven’t spent that much time honing the performance of generic data structures like hashes and dictionaries. This isn’t because we don’t want them to be fast (we do), but because they’re not as important as they are in a language like Python where they’re your only option. In Julia, when performance counts, your best bet is often to use a different, better suited data structure. In this case, @traktofon’s post showed that you can get a huge speedup that way – far faster than you could ever get with generic data structures, no matter how much we hone them.

---

<div class="post-metadata">

**Author:** ![mbeltagy](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mbeltagy/32/130_2.png) [@mbeltagy](https://discourse.julialang.org/u/mbeltagy)\
**Post date:** [March 7, 2017, 6:44am UTC](https://discourse.julialang.org/t/fast-string-processing-in-julia-vs-python/2443/37 "2017-03-07T06:44:31Z")

</div>

Thanks @StefanKarpinski  
I really learned a great deal here. I am appreciating how Julia works and how best to put its power to effective use.  
I tested on 0.5 and 0.6 (master branch). The results were very similar.  
For the original code that I first posted, total execution was `52` seconds for 0.5 and `54` for 0.6.  
For the one that uses sets (more comparable to Python) it was `5.3` and `5.4` seconds.  
As far I as I can tell, the difference is quite minimal between the two versions.

In the code below, I just timed the `main` function after warmup.

```julia
using Combinatorics

count_o(s,l)=count(x->x==l,s)
cross_(A, B)=["$a$b" for a in A for b in B]
function combos(items, n)
    combs=combinations(items,n)
    res=Vector{String}(length(combs))
    map!(x->join(x," "),res,collect(combs))
end

function P(event, space)
    event_ = such_that(event, space)
    length(intersect(event_,Set(space)))//length(space)
end

function such_that(predicate::Function, collection)
    filter(predicate,collection)
end;

suits = "SHDC"
ranks = "A23456789TJQK"

function flush(hand)
    s::String=suits
    any(count_o(hand,suit) == 5 for suit in s)
end

function main()
    deck = cross_(ranks, suits)
    Hands = combos(deck, 5) #A massive list of all possible hands
    P(flush, Hands) #Warm up
end

```

---

<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:** [March 7, 2017, 2:48pm UTC](https://discourse.julialang.org/t/fast-string-processing-in-julia-vs-python/2443/38 "2017-03-07T14:48:26Z")

</div>

6 posts were split to a new topic: [ANN: Cards.jl](https://discourse.julialang.org/t/ann-cards-jl/2523)

---

<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:** [March 7, 2017, 2:51pm UTC](https://discourse.julialang.org/t/fast-string-processing-in-julia-vs-python/2443/39 "2017-03-07T14:51:26Z")

</div>

I’ve split the discussion of my new [Cards.jl package](https://github.com/StefanKarpinski/Cards.jl) into a [new thread](https://discourse.julialang.org/t/ann-cards-jl/2523).

[Previous page](https://discourse.julialang.org/t/fast-string-processing-in-julia-vs-python/2443.md?page=1)