So I was hacking together a tool to chew through a CSV file and was considering performance as I’ll have to process something in the vicinity of 11 million rows. So I was playing around with a simple script to figure out how unique a column was. So, a nice-looking Crystal version:
Processed 1038785 rows in 2.5482900969999998 sec, 407640.00975513743 per sec
Then I let Gemini port it to PHP:
Processed 1038785 rows in 0.42527914047241 sec, 2442595.7004289 per sec
What the…? Crystal massively outpaced by an interpreted language?
Tried recompiling with --release --production:
Processed 1038785 rows in 0.68309683 sec, 1520699.488533712 per sec
Better, but still pretty pathetic next to PHP. Trying commenting out things, I found that the major time sink was cols = line.split(SEPARATOR). I know, it allocates a new array of strings, and there’s more effective ways to do it when optimizing, but it’s up against $cols = explode(self::SEPARATOR, rtrim($line, "\r\n")); which does the same thing.
Is String#split really that slow? (I tried splitting both with a String and a Char separator).
This is strange because, on LangArena benchmark Etc::Words is essentially only @text.split(' ') { |w| frequencies.update(w, &.+(1)) }, as you can see Crystal fastest in this test among 22 languages.
Interpreted vs. compiled isn’t really that relevant in this case. We’re talking about the performance of a built-in function of PHP which is implemented in C. And it’s probably implemented quite efficiently. Perhaps more efficiently than String#split.
It seems String#split misses a couple of optimizations. For example, when the separator is a single byte (or single-byte optimizable), which seems to apply to your use case?
There could also be some differences in the runtime, e.g. the efficiency of allocating strings. I presume there’s probably not much difference there, though. Or maybe PHP is at a bit of a disadvantage due to the interpreter overhead.
Which would imply that PHP is faster than a number of compiled languages. Maybe the block version is faster?
You’re right, if I comment out the split and use hardcoded strings as a placeholder, things speeds up considerably.
# crystal run
Processed 1038786 rows in 0.323526817 sec, 3210818.842259991 per sec
# --release --production
Processed 1038786 rows in 0.069133719 sec, 15025750.314401574 per sec
# PHP
Processed 1038786 rows in 0.12817907333374 sec, 8104177.7958194 per sec
But PHP is still more than twice as fast than un-optimized Crystal.
It would seem that PHP is pretty well optimized for this case, tried having Gemini do a NodeJS version of the original script:
Processed 1038785 rows in 1.5042152469999999 sec, 690582.6822801777 per sec
Half the speed of PHP, but still faster than un-optimized Crystal.
Yeah, it’s just splitting on commas. The PHP version seems awfully simple, but simple often helps hardware optimization.
# TODO: Write documentation for `Uniq`
module Uniq
VERSION = "0.1.0"
SEPARATOR = ','
MAX_ITERATIONS = 1_500_000
OUTPUT_EVERY = 100_000
def self.main(args : Array(String))
file = args[0]?
abort("please provide a file") unless file
isbns = Set(String).new
processed : Int32 = 0
start_time = Time.instant
File.open(file, "r").each_line do |line|
break if processed >= MAX_ITERATIONS
cols = line.split(SEPARATOR)
next if cols[0] == "ISBN"
processed += 1
isbns << cols[0]
put_status(start_time, processed) if processed % OUTPUT_EVERY == 0
end
puts "Done"
puts ""
puts "#{processed} ISBN numbers, #{isbns.size} unique"
put_status(start_time, processed)
end
def self.put_status(start_time : Time::Instant, processed : Int32)
end_time = Time.instant
seconds = end_time.duration_since(start_time).total_seconds
rate = processed / seconds
puts "Processed #{processed} rows in #{seconds} sec, #{rate} per sec"
end
end
Uniq.main(ARGV)
The CSV has 7 columns, but the script only cares about the first. I can’t share the CSV I’ve used, the 165MiB size being one factor, but it shouldn’t be to hard to generate something.
There’s no useful performance data without --release, unfortunately. Compile-time optimizations are where the majority of a program’s performance comes from. The PHP interpreter you’re using almost certainly has them enabled.
An unoptimized Crystal program can’t be faster than an interpreted language when the latter spends most of its time in optimized compiled code.
Are you comparing String#split against mb_str_split() that are both Unicode aware, or to str_split() that expects ASCII? The latter can be much more optimized.
The comparison is with explode, not str_split. It seems explode is also Unicode aware. But it really doesn’t matter because the separator is a single ASCII character and it can be implemented with memchr (which the PHP engine does, String#split does not).
memchr typically utilizes SIMD instructions so it’s much more efficient than iterating each byte. We could easily do that in String#split, too.
I implemented a byte-based loop for separators that are ASCII characters. It seems promising except when the splitted parts are very short (M < 10). I also tried to use the single-pass Rabin-Karp algorithm from this related PR for multibyte separators, and the results are slower than the existing naive loop for some reason.
However:
If this is the case then #partition or even #index is enough, and the Crystal code will probably be on par with a PHP equivalent.
I tried something similar the other night after seeing this thread and had the same results. Byte-by-byte iteration, precise allocations (no reallocs), and somehow it was slower than stdlib String#split for the inputs I tried. That was really surprising.
One thing that was a little over 3x as fast in the 1000x1000 case, though, was combining the precise allocations from that idea with a SWAR implementation based on ideas I got from this blog post along with a bitmask to find occurrences of the separator.
Python (called here): memchr for single bytes but plain loop for subjects shoter than MEMCHR_CUT_OFF bytes, modified Boyer-Moore / Horspool for short subjects or separators, two-way algorithm for long matches, and an adaptive algorithm between the two when the separator is longer than 33% of the subject