Malice
2/8/2016 11:58:00 PM
On Tuesday, 9 February 2016 00:05:18 UTC+1, Antsan wrote:
> Am Montag, 8. Februar 2016 20:04:18 UTC+1 schrieb Malice:
> > So I am toying with hash table performance in CL. I am curious how I can make it as fast as possible(and optimization in CL in general).
> >
> > I created few scripts in different languages to compare their speed:
> > Each program puts 10kk(millions) of numbers from 0 to 10kk-1 into hash table. Number at ith position is i. Afterwards, I print the value of 150 000th number.
> > I run each test 1000 times to get average time of execution.
> >
> > Common Lisp:
> >
> > (defun test ()
> > (declare (optimize (speed 3) (safety 0)))
> > (let* ((size 10000000)
> > (x (make-hash-table :test #'eq :size size)))
> > (loop for i from 0 to size do
> > (setf (gethash i x) i))
> > (print (gethash 150000 x))))
> >
> > (save-lisp-and-die "test.elf" :toplevel #'test :executable t :compression 9)
> >
> > command used to test: time for i in {1.1000}; do ./test.elf ; done
> > Result: ~1.059 seconds
> > SBCL version: 1.3.1
> >
> > Python:
> >
> > #!/usr/bin/python
> >
> > if __name__ == "__main__":
> > x = {}
> > size = 10000000
> > for i in xrange(size):
> > x[i] = i
> > print(x[150000])
> >
> > command used to test: time for i in {1.1000}; do ./hash.py ; done
> > Result: ~1.333 seconds
> > Interpreter version: 2.7.10
> >
> > C++11:
> >
> > #include <iostream>
> > #include <unordered_map>
> >
> > int main(int argc, char* argv[])
> > {
> > unsigned long size = 10000000L;
> > std::unordered_map<unsigned long, unsigned long> x;
> > x.reserve(size);
> > for(unsigned long i = 0; i < size; ++i)
> > {
> > x[i] = i;
> > }
> > std::cout << x[150000] << std::endl;
> > return 0;
> > }
> >
> > Compiled with: g++ hash.cpp -o hashcpp.elf -std=c++11 -O3
> > Compiler version: gcc 4.8.5
> > Command used to test: time for i in {1..1000}; do ./hashcpp.elf ; done
> > Result: 0.775 seconds
> >
> > I tried Ruby, but some obvious ways were too slow(~7 seconds).
> >
> >
> > So, as you can see - CL is faster from python, but C++ is still faster from CL. How can I make it even faster, so the difference is minimal?
> >
> > I didn't try to compare with other languages, but you're free to take this code and run on your machine to present benchmarks; preferably functional languages.
> >
> > What could I do to speed CL up?
>
> Your test is non-conforming. Two numbers must not be considered equal under EQ.
> The hash-table needs to use EQL as a test predicate.
>
> There is a print expression, but did you actually check that it returns what you
> expect?
My bad then. However, in my implementation eq works fine, and all the programs have the same observable behaviour - they print 150000 and a newline.
But am I missing something, or is it that numbers *might* be (sometimes) considered equal under eq, but that's implementation-dependant?