int compare(const void* l, const void* r){
char* cl = *(char**)l+8;
char* cr = *(char**)r+8;
return strcmp(cl, cr);
}
void str_qsort(char **strings, size_t len) { /* you need to pass len here */
/* qsort(strings, len, sizeof(char*), (int (*)(void*, void*))strcmp); */
qsort(strings, len, sizeof(char*), compare);
}
"""
const Clib = "strqsort" # tempname() # make a temporary file
# compile to a shared library by piping C_code to gcc
# (works only if you have gcc installed):
open(`gcc -fPIC -O3 -msse3 -xc -shared -o $(Clib * "." * Libdl.dlext) -`, "w") do f
print(f, C_code)
end
# define a Julia function that calls the C function:
str_qsort(X::Array{String}) = ccall(("str_qsort", Clib), Void, (Ptr{UInt64}, Cint), reinterpret(Ptr{UInt64}, pointer(X)), length(X))
a = [String([Char(i)]) for i in 'Z':-1:'A']
println("before sort: $a")
@btime str_qsort(a)
println("after sort: $a")
const M=100_000_000; const K=100
srand(1)
svec1 = rand([string(rand(Char.(32:126), rand(1:8))...) for k in 1:M÷K], M)
l = length(svec1)
println("before sort: length=$l")
for i in 1:length(svec1)-1
if svec1[i]>svec1[i+1]
println("it is ok now to have unordered strings! svec1[$i]>svec1[$(i+1)] \"$(svec1[i])\">\"$(svec1[i+1])\"")
break
end
end
@btime str_qsort(svec1)
l = length(svec1)
println("after sort length=$l")
global sorted = true
for i in 1:length(svec1)-1
if svec1[i]>svec1[i+1]
println("error svec1[$i]>svec1[$(i+1)] $(svec1[i])>$(svec1[i+1])")
sorted = false
break
end
end
println(sorted ? "sorted! :)" : "unsorted! :(")
```
---
### Author:  [@xiaodai](https://discourse.julialang.org/u/xiaodai)
#### Post date: [December 25, 2017, 11:34pm UTC](https://discourse.julialang.org/t/how-to-make-a-c-function-compiled-by-myself-available-to-ccall/7972/27 "2017-12-25T23:34:56Z")
> [@Liso](#):
>
> charstarstar.(1:2) will create new vector. So your radix\_sort will sort something unnamed and temporary.
yeah i realised after sorting in c but in Julia the string didn’t change. The radixsort implementation doesnt use `charstarstar`.
---
### Author:  [@JeffreySarnoff](https://discourse.julialang.org/u/JeffreySarnoff)
#### Post date: [December 26, 2017, 2:58am UTC](https://discourse.julialang.org/t/how-to-make-a-c-function-compiled-by-myself-available-to-ccall/7972/28 "2017-12-26T02:58:25Z")
> [@Liso](#):
>
> const Clib = “strqsort” # tempname() # make a temporary file
good example …
`const Clib = "./strqsort"` worked better for me on Linux
---
### Author:  [@xiaodai](https://discourse.julialang.org/u/xiaodai)
#### Post date: [December 26, 2017, 3:02am UTC](https://discourse.julialang.org/t/how-to-make-a-c-function-compiled-by-myself-available-to-ccall/7972/29 "2017-12-26T03:02:50Z")
> [@Liso](#):
>
> @btime str\_qsort(svec1)
should the above be `@btime str_qsort($svec1)` instead? As `svec1` gets modified after first run. Also `str_qsort` should be called `str_qsort!`. Also on my computer that sort takes 48 seconds but FastGroupBy’s `radixsort!` only took 19~29 seconds.
```julia
const M=100_000_000; const K=100
using FastGroupBy
srand(1)
svec1 = rand([string(rand(Char.(32:126), rand(1:8))...) for k in 1:M÷K], M)
@time FastGroupBy.radixsort!(svec1) # 29 seconds
issorted(svec1)
```
My [`cradixsort!`](https://discourse.julialang.org/t/wip-faster-string-sort/7671/45) performs poorly atm at 39~50 seconds.
---
### Author:  [@Liso](https://discourse.julialang.org/u/Liso)
#### Post date: [December 26, 2017, 10:29am UTC](https://discourse.julialang.org/t/how-to-make-a-c-function-compiled-by-myself-available-to-ccall/7972/30 "2017-12-26T10:29:59Z")
> [@xiaodai](#):
>
> should the above be @btime str\_qsort($svec1) instead? As svec1 gets modified after first run. Also str\_qsort should be called str\_qsort!. Also on my computer that sort takes 48 seconds but FastGroupBy’s radixsort! only took 19~29 seconds.
Thanks! 🙂 I didn’t know about `$` and you are right about `!` too.
I just cloned your FastGroupBy package ( `Pkg.clone("https://github.com/xiaodaigh/FastGroupBy.jl.git")`) …
Benchmarks are complicated things because my results are `6.242 s (29 allocations: 2.24 GiB)` for `radixsort!` and `8.997 s (0 allocations: 0 bytes)` for `str_qsort!`.
Seems that our HW/SW configurations are different so are our benchmarks too…
But anyway - good result for `radixsort!`! 😃
---
### Author:  [@xiaodai](https://discourse.julialang.org/u/xiaodai)
#### Post date: [December 26, 2017, 11:10am UTC](https://discourse.julialang.org/t/how-to-make-a-c-function-compiled-by-myself-available-to-ccall/7972/31 "2017-12-26T11:10:09Z")
i need a benchmark suite that collect other info. i wonder what set up you have? i have a core i7 laptop with 4 cores and 32G of RAM
---
### Author:  [@Liso](https://discourse.julialang.org/u/Liso)
#### Post date: [December 26, 2017, 11:19am UTC](https://discourse.julialang.org/t/how-to-make-a-c-function-compiled-by-myself-available-to-ccall/7972/32 "2017-12-26T11:19:04Z")
core i5 8GB RAM Ubuntu16.04 64 bit
it is really interesting that my results are so better than yours! (windows vs ubuntu doesn’t seems to be cause or…?)
I hope we found here some more volunteers! 😛
---
### Author:  [@Liso](https://discourse.julialang.org/u/Liso)
#### Post date: [December 26, 2017, 11:23am UTC](https://discourse.julialang.org/t/how-to-make-a-c-function-compiled-by-myself-available-to-ccall/7972/33 "2017-12-26T11:23:10Z")
Thanks! 🙂 On my ubuntu it works without `./` and put `strqsort.so` locally…
I was using `\path_to_julia(0.6/0.7)\julia str_qsort.jl` …
Could you please do benchmark on your machine? If it possible then with xiaodai’s `radixsort!` too? Thanks! 🙂
---
### Author:  [@JeffreySarnoff](https://discourse.julialang.org/u/JeffreySarnoff)
#### Post date: [December 26, 2017, 4:47pm UTC](https://discourse.julialang.org/t/how-to-make-a-c-function-compiled-by-myself-available-to-ccall/7972/34 "2017-12-26T16:47:18Z")
linux flavor : Linux Mint 18.2 Sonya
processor : Intel Quad Core i7-6820HK
clock freqs : 2700 / 3600 MHz (base/max)
caches: 32K, 256K, 8192K
memory: 64G
---
### Author:  [@Liso](https://discourse.julialang.org/u/Liso)
#### Post date: [December 26, 2017, 11:08pm UTC](https://discourse.julialang.org/t/how-to-make-a-c-function-compiled-by-myself-available-to-ccall/7972/35 "2017-12-26T23:08:50Z")
How is it possible that my worse HW could get better results? Did you benchmark with `@time` or `@btime`? on global namespace?
I was trying to get similar results and below are my two experiments.
`@time` → **14.436537 seconds** (33 allocations: 2.238 GiB, 19.33% gc time)
`@time` on sorted array → **5.801548 seconds** (33 allocations: 2.238 GiB, 5.04% gc time)
`@btime` → **5.601 s** (29 allocations: 2.24 GiB)
Do I still use BenchmarkTool wrong?
```julia
_
_ _ _(_)_ | A fresh approach to technical computing
(_) | (_) (_) | Documentation: https://docs.julialang.org
_ _ _| |_ __ _ | Type "?help" for help.
| | | | | | |/ _' | |
| | |_| | | | (_| | | Version 0.6.1 (2017-10-24 22:15 UTC)
_/ |\ __'_|_|_|\__'_| | Official http://julialang.org/ release
|__/ | x86_64-pc-linux-gnu
julia> using FastGroupBy
julia> const M = Int(1e8); const K = 100;
julia> srand(1);
julia> svec1 = rand(["i"*dec(k,7) for k in 1:M÷K], M);
julia> @time radixsort!(["a"])
0.414596 seconds (148.40 k allocations: 8.834 MiB)
julia> @time radixsort!(["a"])
0.000210 seconds (11 allocations: 1.001 MiB)
julia> @time radixsort!(svec1)
14.436537 seconds (33 allocations: 2.238 GiB, 19.33% gc time)
julia> @time radixsort!(svec1) # now svec1 is sorted
5.801548 seconds (33 allocations: 2.238 GiB, 5.04% gc time)
```
```julia
_ _ _(_)_ | A fresh approach to technical computing
(_) | (_) (_) | Documentation: https://docs.julialang.org
_ _ _| |_ __ _ | Type "?help" for help.
| | | | | | |/ _' | |
| | |_| | | | (_| | | Version 0.6.1 (2017-10-24 22:15 UTC)
_/ |\ __'_|_|_|\__'_| | Official http://julialang.org/ release
|__/ | x86_64-pc-linux-gnu
julia> using FastGroupBy
julia> using BenchmarkTools
julia> srand(1);
julia> const M = Int(1e8); const K = 100;
julia> svec1 = rand(["i"*dec(k,7) for k in 1:M÷K], M);
julia> @btime radixsort!($svec1)
5.601 s (29 allocations: 2.24 GiB)
```
---
### Author:  [@JeffreySarnoff](https://discourse.julialang.org/u/JeffreySarnoff)
#### Post date: [December 27, 2017, 12:03am UTC](https://discourse.julialang.org/t/how-to-make-a-c-function-compiled-by-myself-available-to-ccall/7972/36 "2017-12-27T00:03:02Z")
I was measuring apples with an orange ruler and
```julia
julia> Pkg.status("BenchmarkTools")
- BenchmarkTools 0.2.2
julia> versioninfo()
julia> versioninfo()
Julia Version 0.6.2
Commit d386e40c17 (2017-12-13 18:08 UTC)
Platform Info:
OS: Linux (x86_64-pc-linux-gnu)
CPU: Intel(R) Core(TM) i7-6820HK CPU @ 2.70GHz
WORD_SIZE: 64
...
LLVM: libLLVM-3.9.1 (ORCJIT, skylake)
```
run this on v0.6.2:
```julia
using BenchmarkTools
using FastGroupBy
C_code = raw"""
#include
#include
#include
int compare(const void* l, const void* r){
char* cl = *(char**)l+8;
char* cr = *(char**)r+8;
return strcmp(cl, cr);
}
void str_qsort(char **strings, size_t len) { /* you need to pass len here */
/* qsort(strings, len, sizeof(char*), (int (*)(void*, void*))strcmp); */
qsort(strings, len, sizeof(char*), compare);
}
""";
const Clib = "./strqsort" # tempname() # make a temporary file
# compile to a shared library by piping C_code to gcc
# (works only if you have gcc installed):
open(`gcc -fPIC -O3 -msse3 -xc -shared -o $(Clib * "." * Libdl.dlext) -`, "w") do f
print(f, C_code)
end
# define a Julia function that calls the C function:
str_qsort(X::Array{String}) =
ccall(("str_qsort", Clib), Void, (Ptr{UInt64}, Cint), reinterpret(Ptr{UInt64}, pointer(X)), length(X))
# !! M is 10 million !!
const M=10_000_000; const K=100;
srand(1);
svec1 = rand([string(rand(Char.(32:126), rand(1:8))...) for k in 1:M÷K], M);
svec2 = copy(svec1);
svec3 = copy(svec1);
fastest_qsort = (@benchmark str_qsort($svec1)).times[1];
fastest_sort = (@benchmark sort!($svec2)).times[1];
fastest_radixsort = (@benchmark FastGroupBy.radixsort!($svec3)).times[1];
qsort_secs = round(fastest_qsort / 1e9, 4);
sort_secs = round(fastest_sort / 1e9, 4);
rsort_secs = round(fastest_radixsort / 1e9, 4);
issorted(svec2) && println("sort seconds: $sort_secs");
issorted(svec1) && println("qsort seconds: $qsort_secs");
issorted(svec3) && println("rsort seconds: $rsort_secs");
```
I see
```julia
sort seconds: 0.8236
qsort seconds: 0.5173
rsort seconds: 0.399
```
restarting and running the same code with `M = 100_000_000`:
```julia
sort seconds: 10.4221
qsort seconds: 6.2238
rsort seconds: 4.1681
```
What do you see on your machine?
---
### Author:  [@xiaodai](https://discourse.julialang.org/u/xiaodai)
#### Post date: [December 27, 2017, 1:13pm UTC](https://discourse.julialang.org/t/how-to-make-a-c-function-compiled-by-myself-available-to-ccall/7972/37 "2017-12-27T13:13:45Z")
I see very similar timing and that your computer is a abit faster than mine but the order of the sorts is the same.
---
### Author:  [@JeffreySarnoff](https://discourse.julialang.org/u/JeffreySarnoff)
#### Post date: [December 27, 2017, 3:06pm UTC](https://discourse.julialang.org/t/how-to-make-a-c-function-compiled-by-myself-available-to-ccall/7972/38 "2017-12-27T15:06:28Z")
Right.
Assume that others see much the same when running this on distinct technological platforms. With that [presumed] additional evidence, we may hypothesize [and use Julia to fit] a loosely affine invariance that transforms timings for each of these algorithms on one platform to another. Better still, we do not need any explicit statement of these relationships – just consistent and non-contradictory evidence.
Given, after a fashion, all of the above, the algorithms’ relative timings inform.
---
### Author:  [@xiaodai](https://discourse.julialang.org/u/xiaodai)
#### Post date: [December 30, 2017, 2:28am UTC](https://discourse.julialang.org/t/how-to-make-a-c-function-compiled-by-myself-available-to-ccall/7972/39 "2017-12-30T02:28:15Z")
Just wrote a simple guide for Windows users
[https://www.codementor.io/zhuojiadai/making-compiling-c-functions-for-use-in-julia-on-windows-f9lwa5i43](https://www.codementor.io/zhuojiadai/making-compiling-c-functions-for-use-in-julia-on-windows-f9lwa5i43)
---
### Author:  [@Liso](https://discourse.julialang.org/u/Liso)
#### Post date: [December 30, 2017, 8:50am UTC](https://discourse.julialang.org/t/how-to-make-a-c-function-compiled-by-myself-available-to-ccall/7972/40 "2017-12-30T08:50:23Z")
Fantastic! 🙂
But be aware! `LD_LIBRARY_PATH` could represent more paths! (on unix systems `:` is separator)
```julia
env_path = ENV["LD_LIBRARY_PATH"]
clibname = "addc"
const Clib = joinpath(env_path,clibname) # WARNING!!!
```
BTW I am curious if we could do something better with calling LLVM inline assembly (see for example [Andrew Cooke: C[omp]ute](http://acooke.org/cute/InlineAsse0.html) ).
For start I am thinking about radix calculation. It could be good if we could avoid function calling overhead (although I am not sure if `Base.llvmcall` could help).
[Previous page](https://discourse.julialang.org/t/how-to-make-a-c-function-compiled-by-myself-available-to-ccall/7972.md?page=1)