freenode/lisp - IRC Chatlog
Search
9:08:56
russellw
I just discovered something weird. On theoretical grounds, vectors should be faster than lists, right? Well, tried a simple test just now in SBCL, find vs member, and lists are faster... by 3 orders of magnitude
9:19:43
russellw
The above is also true of CCL. Presumably they just put much more effort into optimizing lists
9:22:08
russellw
it absolutely does not sound right, to the point where I would've not believed it had I not seen the results myself, so I would definitely encourage you to try it
9:22:11
russellw
(time(dotimes(i 100000000)(find 'z #(a b c d e f g h i j k l m n o p q r s t u v w x y z))))
9:22:31
russellw
(time(dotimes(i 100000000)(member 'z '(a b c d e f g h i j k l m n o p q r s t u v w x y z))))
9:25:23
beach
russellw: In SBCL with a million elements, using FIND on the list and on the vector gives indistinguishable times.
9:26:07
russellw
beach, in practice you would use a hash table with 1000000 elements. The above is not an artificial test; it reflects a real pattern that I use somewhat frequently, which is why I was interested in the relative times. I think we both know compilation time is not going to be significant here, but I would by all means encourage you or anyone else interested, to try variants of the test and report
9:26:23
russellw
the compiler does not remove the code entirely, as can be verified by trying different loop counts
9:27:00
russellw
indistinguishable times with a million elements is an interesting data point; it is at least considerably closer to what one would expect
9:27:07
beach
Anyway, you can not design a performance test that way. It will measure something else.
9:28:27
russellw
there is no such thing as a perfect performance test, but I think the above is sufficient grounds to drop my tentative plan to start using find instead of member
9:28:30
beach
With 10 million elements, find gives 0.080 seconds in one case and 0.079 in the other.
9:29:37
beach
But this result only reflects the fact that MEMBER is better optimized than FIND. Not that any of the data types is "faster" than the other.
9:31:00
russellw
So not as outlandish, but still interestingly different from what would expect on theoretical grounds. and if X is better optimized than Y, then X tends to end up faster than Y. That's the whole point of optimization. And was also my suggested explanation in the first place
9:33:15
russellw
which they clearly did, as your own results verified. the same function was the same speed on lists and vectors in the asymptotic case, which you only get if you put more optimization into lists, that by default would be slower
9:36:52
nydel
russellw: if you compose a hypothesis to mark the beginning of these tests, what is it, and is it proven? if so, have you tried to disprove it?
9:38:07
russellw
nydel, my hypothesis was that vectors would be faster than lists for testing membership. That hypothesis has been comprehensively disproven
9:40:13
ggole
If this operation is consuming a lot of time, you could (probably) do a lot better than switching between member and find
9:41:38
russellw
ggole, with many elements yes, or a hash table as I mentioned, but I am looking at scenarios where there would only be a handful of elements. Constant factors matter when N is small
9:42:38
scymtym
here, all three examples compile to the same (empty bodied) loop and take the same time to execute. this is not surprising as the compiler can fold ({member,find} 'z '(… z))
9:44:53
russellw
then what did you do differently? because it did not optimize away the loop body when I tried it
9:47:42
russellw
I did not wrap it in a lambda, which you just did. So I was wondering if that made the difference. But I just tried your version now...
9:48:56
scymtym
taking time proportional to the iteration count only means that the loop wasn't optimized away entirely. the body still could be and indeed is
9:49:59
russellw
well the constant of proportionality was a lot more than an empty loop. Anyway, the disassembly I just posted, does not look to me like the loop body was optimized away. This is with a recent version of the compiler.
12:43:44
beach
I would prefer something like INCLUDE and EXCLUDE for symmetry. But it's moot. We have what we have.
12:50:50
ggole
The nice thing about remove/remove-if is that the name fits beautifully for the non-function case, which is not really true of select
13:05:21
warweasle
I used the time machine. The closest I could get everything back to normal ended up with Trump. Frankly, I just quit trying after that.
15:21:45
beach
vtomole: There is now a #sicl IRC channel where I can blab freely about what I am doing.
15:23:20
beach
I am making very good progress on bootstrapping, and since Clasp seems to want to replace LLVM (which is very slow) by Common Lisp code generating x86-64, I am working on HIR-to-MIR which will eventually be possible to translate to x86-64.
15:28:44
vtomole
beach: Replacing LLVM in Clasp seems like a huge project. Good luck to those involved! Why is it slow?
15:29:28
beach
Luckily, we don't have to replicate all of LLVM. Having said that, I am convinced that it would be much easier to write something like that in Common Lisp than in C++.
15:30:16
beach
I often say "it is impossible to write a C++ program that is both modular and fast", and here is another data point in that direction.
15:30:46
beach
astalla: That's what I would have thought, but drmeister says that he can handle that.
15:34:39
djeis[m]
Generating code to access C++ directly is a lot more complicated than just what you can get with CFFI, because C++ is all kinds of nonsense at the ABI level.
15:35:17
astalla
vtomole: as far as I know, to properly link to C++ code without second-guessing whatever compiler was used to compile it, you need a C++ parser, and C++ syntax is complex enough that a proper parser is very hard to write and basically it requires a whole C++ compiler.
15:36:34
djeis[m]
Not just a C++ parser, you have to replicate the name mangling proceedure of whatever C++ compiler that lib was compiled with.
15:36:46
beach
I had assumed that LLVM was a requirement for such interoperability to work, but I only recently learned that drmeister had plans to generate x86-64 code directly.
15:38:11
djeis[m]
I'm fairly certain that LLVM would still be needed for the interop itself, but there's no reason that codegen for the bits that don't involve interop could be done using some other compiler.
15:48:01
beach
djeis[m]: drmeister (who is my house guest at the moment) says that all that is required is to follow the calling convention, which is fairly easy.
15:54:32
ggole
For instance, there's a trick which clang(?) does where if every override for a virtual function returns a constant, they replace the function pointer with the relevant constant in the vtables
15:55:07
ggole
If you have to reverse-engineer that sort of implementation quirk, you'll be in for quite a ride.
16:39:33
Shinmera
razzy: please try not to keep off-topic chatter going, especially when it's politically charged.
16:40:13
russellw
what's the best way to test a variable for being equal to one of several strings? with symbols it's (member x '(a b c)) but that uses eql so doesn't work with strings
16:42:54
shka_
data frame implementation i am working on, will use copy on write logic to only copy parts of data frame that are actually changed
16:43:40
shka_
however, obviously, it would be beneficial to check if operation on frame actually changes it
20:30:04
Myon
svillemot: Hi, are you taking over cl-nibbles from dim, or should I try uploading the fixes for https://bugs.debian.org/cgi-bin/bugreport.cgi?bug=908641 ?
20:31:27
drmeister
On reflection, generating code directly from cleavir will probably require figuring out how to set up unwinding and to generate DWARF metadata.