00:00:00 huangjs [~huangjs@190.8.100.83] has joined #sbcl 00:13:52 antgreen [~user@CPE0021910f07ac-CM0019477f82fc.cpe.net.cable.rogers.com] has joined #sbcl 00:28:38 francisl [~flavoie@bas1-montreal48-1176173836.dsl.bell.ca] has joined #sbcl 00:31:22 -!- slyrus_ [~chatzilla@173-228-44-92.dsl.static.sonic.net] has quit [Ping timeout: 256 seconds] 00:32:20 -!- Quadrescence is now known as booklet 01:16:58 echo-area [~user@182.92.247.2] has joined #sbcl 01:19:29 -!- gko [~gko@114-34-168-13.HINET-IP.hinet.net] has quit [Ping timeout: 252 seconds] 02:20:43 -!- antgreen [~user@CPE0021910f07ac-CM0019477f82fc.cpe.net.cable.rogers.com] has quit [Remote host closed the connection] 02:28:29 gko [~gko@220.228.255.204] has joined #sbcl 02:35:49 -!- rpg [~rpg@216.243.156.16.real-time.com] has quit [Quit: rpg] 03:16:32 saschakb_ [~saschakb@p4FEA0FA5.dip0.t-ipconnect.de] has joined #sbcl 03:16:34 blackwol` [~blackwolf@ool-4575fc51.dyn.optonline.net] has joined #sbcl 03:18:58 -!- saschakb [~saschakb@p4FEA10DE.dip0.t-ipconnect.de] has quit [Read error: Operation timed out] 03:20:30 -!- blackwolf [~blackwolf@ool-4575fc51.dyn.optonline.net] has quit [Ping timeout: 260 seconds] 04:05:16 nikodemus [~nikodemus@178-55-57-180.bb.dnainternet.fi] has joined #sbcl 04:05:16 -!- ChanServ has set mode +o nikodemus 04:33:26 slyrus_ [~chatzilla@99-28-161-110.lightspeed.miamfl.sbcglobal.net] has joined #sbcl 04:54:50 good morning 04:56:15 evening nikodemus 05:03:50 angavrilov [~angavrilo@217.71.227.190] has joined #sbcl 05:14:51 les [moreorles@lesharris.com] has joined #sbcl 05:21:25 -!- les_ [moreorles@lesharris.com] has quit [*.net *.split] 05:21:26 -!- edgar-rft [~user@HSI-KBW-078-043-123-191.hsi4.kabel-badenwuerttemberg.de] has quit [*.net *.split] 05:21:26 -!- flip214 [~marek@unaffiliated/flip214] has quit [*.net *.split] 05:21:26 -!- kwmiebach__ [~kwmiebach@164-177-155-66.static.cloud-ips.co.uk] has quit [*.net *.split] 05:21:26 -!- froydnj [nfroyd@people.mozilla.com] has quit [*.net *.split] 05:21:26 -!- asedeno_work [~asedeno@74.125.59.113] has quit [*.net *.split] 05:21:26 -!- homie [~levgue@xdsl-78-35-148-224.netcologne.de] has quit [*.net *.split] 05:21:26 -!- antoszka [~antoszka@unaffiliated/antoszka] has quit [*.net *.split] 05:21:27 -!- nikodemus [~nikodemus@178-55-57-180.bb.dnainternet.fi] has quit [*.net *.split] 05:21:27 -!- stassats` [~stassats@wikipedia/stassats] has quit [*.net *.split] 05:21:27 -!- joshee [~joshe@opal.elsasser.org] has quit [*.net *.split] 05:21:27 -!- sshirokov [sshirokov@2600:3c02::f03c:91ff:fe93:e02d] has quit [*.net *.split] 05:21:27 -!- DGASAU [~user@91.218.144.129] has quit [*.net *.split] 05:21:27 -!- dlowe [dlowe@digital.sanctuary.org] has quit [*.net *.split] 05:21:27 -!- gko [~gko@220.228.255.204] has quit [*.net *.split] 05:21:27 -!- francisl [~flavoie@bas1-montreal48-1176173836.dsl.bell.ca] has quit [*.net *.split] 05:21:27 -!- cmm [~cmm@bzq-79-183-234-200.red.bezeqint.net] has quit [*.net *.split] 05:21:27 -!- jsnell [~jsnell@ash.snellman.net] has quit [*.net *.split] 05:22:04 nikodemus [~nikodemus@178-55-57-180.bb.dnainternet.fi] has joined #sbcl 05:22:04 gko [~gko@220.228.255.204] has joined #sbcl 05:22:04 francisl [~flavoie@bas1-montreal48-1176173836.dsl.bell.ca] has joined #sbcl 05:22:04 stassats` [~stassats@wikipedia/stassats] has joined #sbcl 05:22:04 edgar-rft [~user@HSI-KBW-078-043-123-191.hsi4.kabel-badenwuerttemberg.de] has joined #sbcl 05:22:04 cmm [~cmm@bzq-79-183-234-200.red.bezeqint.net] has joined #sbcl 05:22:04 asedeno_work [~asedeno@74.125.59.113] has joined #sbcl 05:22:04 flip214 [~marek@unaffiliated/flip214] has joined #sbcl 05:22:04 joshee [~joshe@opal.elsasser.org] has joined #sbcl 05:22:04 kwmiebach__ [~kwmiebach@164-177-155-66.static.cloud-ips.co.uk] has joined #sbcl 05:22:04 jsnell [~jsnell@ash.snellman.net] has joined #sbcl 05:22:04 froydnj [nfroyd@people.mozilla.com] has joined #sbcl 05:22:04 sshirokov [sshirokov@2600:3c02::f03c:91ff:fe93:e02d] has joined #sbcl 05:22:04 DGASAU [~user@91.218.144.129] has joined #sbcl 05:22:04 dlowe [dlowe@digital.sanctuary.org] has joined #sbcl 05:22:04 -!- wolfe.freenode.net has set mode +o nikodemus 05:23:18 -!- les is now known as Guest13199 05:23:59 antoszka [~antoszka@unaffiliated/antoszka] has joined #sbcl 05:26:57 homie [~levgue@xdsl-78-35-148-224.netcologne.de] has joined #sbcl 05:38:14 -!- antifuchs [foobar@care.boinkor.net] has quit [Ping timeout: 272 seconds] 05:38:56 antifuchs [foobar@care.boinkor.net] has joined #sbcl 05:54:39 sdemarre [~serge@91.176.39.207] has joined #sbcl 06:14:58 -!- sdemarre [~serge@91.176.39.207] has quit [Ping timeout: 272 seconds] 06:25:29 -!- nikodemus [~nikodemus@178-55-57-180.bb.dnainternet.fi] has quit [Quit: This computer has gone to sleep] 06:28:04 nikodemus [~nikodemus@178-55-57-180.bb.dnainternet.fi] has joined #sbcl 06:28:20 -!- ChanServ has set mode +o nikodemus 06:32:10 -!- nikodemus [~nikodemus@178-55-57-180.bb.dnainternet.fi] has quit [Client Quit] 07:25:09 -!- gko [~gko@220.228.255.204] has quit [Ping timeout: 245 seconds] 07:31:33 -!- francisl [~flavoie@bas1-montreal48-1176173836.dsl.bell.ca] has quit [Quit: francisl] 08:04:12 -!- antoszka [~antoszka@unaffiliated/antoszka] has quit [Ping timeout: 244 seconds] 08:06:25 antoszka [~antoszka@unaffiliated/antoszka] has joined #sbcl 08:11:57 -!- antoszka [~antoszka@unaffiliated/antoszka] has quit [Ping timeout: 244 seconds] 08:13:18 antoszka [~antoszka@89-77-114-75.dynamic.chello.pl] has joined #sbcl 08:13:19 -!- antoszka [~antoszka@89-77-114-75.dynamic.chello.pl] has quit [Changing host] 08:13:19 antoszka [~antoszka@unaffiliated/antoszka] has joined #sbcl 08:14:28 -!- antoszka [~antoszka@unaffiliated/antoszka] has quit [Read error: Connection reset by peer] 08:15:58 antoszka [~antoszka@unaffiliated/antoszka] has joined #sbcl 08:18:20 -!- borkman [~user@S0106001111de1fc8.cg.shawcable.net] has left #sbcl 08:28:49 saschakb__ [~saschakb@p4FEA06B7.dip0.t-ipconnect.de] has joined #sbcl 08:32:31 -!- saschakb_ [~saschakb@p4FEA0FA5.dip0.t-ipconnect.de] has quit [Ping timeout: 252 seconds] 08:33:40 -!- dsp_ [~dsp@cowpig.ca] has quit [Disconnected by services] 08:42:27 attila_lendvai [~attila_le@178-164-243-62.pool.digikabel.hu] has joined #sbcl 08:42:27 -!- attila_lendvai [~attila_le@178-164-243-62.pool.digikabel.hu] has quit [Changing host] 08:42:27 attila_lendvai [~attila_le@unaffiliated/attila-lendvai/x-3126965] has joined #sbcl 08:55:20 thoughts on making pointer-hash mask out only the bottom (1+ n-fixnum-tag-bits) bits off a descriptor? 08:58:34 homie` [~levgue@xdsl-87-79-192-231.netcologne.de] has joined #sbcl 09:00:10 also, thoughts on switching to a C implementation of SFMT, and just reading bytes off an internal array? 09:01:45 -!- homie [~levgue@xdsl-78-35-148-224.netcologne.de] has quit [Ping timeout: 260 seconds] 09:01:45 http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/SFMT/ <- faster, better distributed, and less vulnerable to "bad" states 09:06:30 or on hashing non-trivial data by copying to a temporary buffer (not even needed for specialised vectors) and then murmurhash-ing that up? 09:11:00 gko [~gko@220.228.255.204] has joined #sbcl 09:18:39 (too bad intel only supports 32bit CRCs) 09:46:18 jdz [~jdz@193.206.22.97] has joined #sbcl 09:57:15 -!- gko [~gko@220.228.255.204] has quit [Read error: Connection reset by peer] 10:24:45 minion [~minion@pppoe.178-66-37-60.dynamic.avangarddsl.ru] has joined #sbcl 10:25:16 minion: what's up? 10:25:24 not much 11:21:10 TimKack [~user@c-2ec22154-74736162.cust.telenor.se] has joined #sbcl 11:37:26 tsuru`` [~charlie@adsl-98-87-50-78.bna.bellsouth.net] has joined #sbcl 11:39:09 -!- tsuru` [~charlie@adsl-74-179-196-101.bna.bellsouth.net] has quit [Ping timeout: 252 seconds] 12:13:23 -!- huangjs [~huangjs@190.8.100.83] has quit [Ping timeout: 255 seconds] 12:26:43 tsuru``` [~charlie@adsl-74-179-28-20.bna.bellsouth.net] has joined #sbcl 12:27:40 -!- tsuru`` [~charlie@adsl-98-87-50-78.bna.bellsouth.net] has quit [Ping timeout: 260 seconds] 12:38:50 -!- blackwol` is now known as blackwolf 12:39:20 -!- attila_lendvai [~attila_le@unaffiliated/attila-lendvai/x-3126965] has quit [Ping timeout: 260 seconds] 12:42:55 gko [~gko@114-34-168-13.HINET-IP.hinet.net] has joined #sbcl 13:01:04 -!- booklet [~quad@unaffiliated/quadrescence] has quit [Quit: Leaving] 13:01:11 attila_lendvai [~attila_le@188-143-63-157.pool.digikabel.hu] has joined #sbcl 13:01:11 -!- attila_lendvai [~attila_le@188-143-63-157.pool.digikabel.hu] has quit [Changing host] 13:01:11 attila_lendvai [~attila_le@unaffiliated/attila-lendvai/x-3126965] has joined #sbcl 13:08:08 Quadresce [~quad@c-24-131-149-41.hsd1.mn.comcast.net] has joined #sbcl 13:08:21 -!- Quadresce [~quad@c-24-131-149-41.hsd1.mn.comcast.net] has quit [Changing host] 13:08:21 Quadresce [~quad@unaffiliated/quadrescence] has joined #sbcl 13:09:59 -!- Quadresce is now known as Quadrescence 13:35:33 -!- echo-area [~user@182.92.247.2] has quit [Read error: Connection reset by peer] 13:37:29 psilord [~psilord@23-25-144-217-static.hfc.comcastbusiness.net] has joined #sbcl 13:44:21 leuler [~user@p549036B0.dip.t-dialin.net] has joined #sbcl 13:47:54 antgreen [user@nat/redhat/x-fbqwflacpbolphsl] has joined #sbcl 13:59:14 francisl [~flavoie@199.84.164.114] has joined #sbcl 14:11:19 pkhuong: About SFMT: I took a new look at the web site and a first one at Mutsuo Saito's thesis. Sounds good. I wasn't aware that it is portable to machines without SSE, too. Also, what I like, is, that it is available in smaller sizes. I think 19937 bits of state is too much for a default common lisp random generator (level-1 cache should better be available for other data). 14:12:22 leuler: I like MT-19937 ;) 14:12:33 plus, it's not like it's hot. 14:13:01 You basically pump 600 dwords of randomness at a time. 14:14:14 leuler: ok, so hashing, next. 14:14:22 -!- attila_lendvai [~attila_le@unaffiliated/attila-lendvai/x-3126965] has quit [Quit: Leaving.] 14:14:53 attila_lendvai [~attila_le@188-143-63-157.pool.digikabel.hu] has joined #sbcl 14:14:53 -!- attila_lendvai [~attila_le@188-143-63-157.pool.digikabel.hu] has quit [Changing host] 14:14:53 attila_lendvai [~attila_le@unaffiliated/attila-lendvai/x-3126965] has joined #sbcl 14:15:32 The 19937 is too arbitrary for my taste. If you like that, you may like the larger state spaces SFMT supports even more? 14:16:16 it would make sense having several PRNG available 14:18:26 stassats`: I can do that, if they can all be coerced into filling a vector of words with random bits. 14:18:45 -!- tsuru``` is now known as tsuru` 14:18:54 ... which kind of eliminates classics like mrg32k3a (although I do have that integer-arithmetic variant ;) 14:20:49 leuler: how about hashing then? Instead of recursing and mixing bits, just blit bits to a temporary buffer and hash that buffer. 14:21:30 Of reasonable PRNG algorithms I know of, the MTs and WELL don't pass all of Ecuyer's TestU01. CMRGs do, but are much slower. 14:21:51 -!- attila_lendvai [~attila_le@unaffiliated/attila-lendvai/x-3126965] has quit [Ping timeout: 260 seconds] 14:22:15 leuler: there isn't much that passes all of TestU ;) 14:22:41 I don't have a strong opinion about whether to support multiple different PRNGs in SBCL; what I would like: If there is only one and it is SFMT, I'd prefer a smaller one. 14:23:00 ok, I'll try to make that a build-time option. 14:23:20 and figure out some way to support both GF(2^k) and double-based PRNGs. 14:23:42 although, really, lecuyer's CMRGs are actually based in modular integer arithmetic. 14:24:27 attila_lendvai [~attila_le@188-143-62-176.pool.digikabel.hu] has joined #sbcl 14:24:27 -!- attila_lendvai [~attila_le@188-143-62-176.pool.digikabel.hu] has quit [Changing host] 14:24:27 attila_lendvai [~attila_le@unaffiliated/attila-lendvai/x-3126965] has joined #sbcl 14:24:36 Maybe I can convince him to derive constants that are good for an integer implementation. IIRC, mrg32k3a's constants were *almost* nicely optimisable. 14:24:47 Passers of TestU (according to my own research): CMRGs, Ecuyer's Tausworthe combined with a Weyl generator, enough CCGs combined. 14:25:15 *pkhuong* wonders where the lagged fibonaccis are ;) 14:28:02 Passers of TestU (I believe): AES in counter mode. Also, I once tried the "mix" part of Murmurhash3 in counter mode and it passed SmallCrush (but only maps one-to-one 64 bits to 64 bits). 14:28:25 leuler: ever murmurhash3's 128 bit output? 14:28:32 oh well, good enough. 14:28:38 The fibonaccis have very short periods compared to the size of their state, which disqualifies them. 14:28:54 I was thinking I'd hash literal values with a variant of zobrist. 14:29:59 I didn't test murmurhash3's 128 bit, no. 14:31:22 anyway, I figure we have better chances of getting decent distribution and speed by copying data to a byte vector and (incrementally) hashing *that8> 14:31:38 * *that*. 14:34:40 Regarding specifically lp 309443: One might get away with keeping the relatively weak "mix" and only improving the hashing of fixnums. For the latter, two fifth of murmur3's fmix might be nice: shr 33 / xor / mul / shr 33 / xor. 14:35:43 attila_lendvai1 [~attila_le@188-143-62-176.pool.digikabel.hu] has joined #sbcl 14:35:43 -!- attila_lendvai [~attila_le@unaffiliated/attila-lendvai/x-3126965] has quit [Disconnected by services] 14:35:44 -!- attila_lendvai1 is now known as attila_lendvai 14:35:44 -!- attila_lendvai [~attila_le@188-143-62-176.pool.digikabel.hu] has quit [Changing host] 14:35:44 attila_lendvai [~attila_le@unaffiliated/attila-lendvai/x-3126965] has joined #sbcl 14:38:32 Passers of TestU: There are folks over in comp.lang.asm.x86 that have fun in finding the smallest algorithms that do just that. See for example http://groups.google.com/group/comp.lang.asm.x86/msg/d0996325ba10d581. 14:41:07 pkhuong: re copying data for hashing: yes. If it's faster or the best way to be able to use something like murmur3, I'm for it. I expect the largest amount of bytes copied is reasonably (with respect to cache sizes) bounded? 14:41:58 * two fifth -> three fifths 14:42:30 leuler: yeah, I was thinking stack-allocate a 1 KB buffer. 14:42:35 vectors can be hashed in-place 14:43:25 OK. 1 KB seems very reasonable to me. 14:44:18 http://arxiv.org/abs/1011.5200 <- says that zobrist-like schemes are surprisingly strong, and not much slower than multiplicative hashing 14:46:31 I just wanted to ask about your zobrist variant. 14:47:34 you know, have 8 vectors of 256 words, lookup in that and xor. 14:47:51 Except, for cache purposes, we probably want 1 vector of 8*256 words (: 14:48:27 or, 256*8 words, rather. 14:56:25 -!- gko [~gko@114-34-168-13.HINET-IP.hinet.net] has quit [Ping timeout: 252 seconds] 14:56:44 -!- homie` [~levgue@xdsl-87-79-192-231.netcologne.de] has quit [Quit: ERC Version 5.3 (IRC client for Emacs)] 14:59:21 That link about zobrist is interesting. I'll need to take my time to read it. 15:03:01 pkhuong: Have you already tried and measured this zobrist thing? I currently (having skimmed the paper only) can't believe that for example for hashing a fixnum it could be as fast as something using one multiplication. I mean, under 64 bits it needs eight cache reads, shifts and mask operations. 15:03:19 their benchmarks are in-cache 15:03:35 so, really... who knows? 15:03:59 But playing with hash table has made me much more concerned with strong hash functions that fast ones. 15:04:11 A fast but bad hash function really ruins your theoretical day. 15:05:27 leuler: for fixnums, we'd probably get away with 2-3 cache reads; the rest would all be zeros ;) 15:07:46 Break out early from the loop over the bytes? Yes, that could well be advantageous for typical fixnums. 15:08:13 no, just set the LUT just right so that zeros are look up next to each other. 15:08:33 About fast vs. good hash functions. I see your point. 15:08:46 so one (or even half, on some uarch) cycle per zero byte. 15:09:02 SBCL's current hash function for fixnums is definitely too weak. 15:09:50 actually, it leads to better-than-expected perf in a lot of practical circumstances (due to its weakness) 15:10:03 how so? 15:10:17 iirc, it kind of preserves order in keys 15:10:31 so close keys -> close buckets. 15:10:45 Bad in theory, good when keys are sequentially accessed. 15:11:10 I'd rather have it be not so good in practice, but never horrible, though. 15:14:32 When are keys sequentially accessed in practice? 15:14:56 not sure... Lots of benchmarks, though (: 15:15:07 :-) 15:17:02 -!- attila_lendvai [~attila_le@unaffiliated/attila-lendvai/x-3126965] has quit [Quit: Leaving.] 15:17:32 -!- antgreen [user@nat/redhat/x-fbqwflacpbolphsl] has quit [Ping timeout: 245 seconds] 15:24:18 gko [~gko@114-34-168-13.HINET-IP.hinet.net] has joined #sbcl 15:25:10 sigh... that uncomfortable time when you don't know if it's our implementation or the underlying theory that sucks. 15:25:34 pkhuong: more specifically? 15:27:01 phd stuff (: 15:27:12 "both" 15:27:31 tell me if you want to hear more about non-differentiable optimisation applied to combinatorial problems ;) 15:27:55 Kryztof: yeah well, the deadline's too close for reviewing th theory. 15:28:25 Sorry, not currently. Also, would be off topic here ;-) 15:30:03 francisl_ [~flavoie@199.84.162.165] has joined #sbcl 15:31:11 leuler: actually, there's this far-fetched plan to apply that to representation selection... 15:31:33 -!- francisl [~flavoie@199.84.164.114] has quit [Ping timeout: 248 seconds] 15:31:34 -!- francisl_ is now known as francisl 15:42:12 i wonder why prngs need to be reimplemented in applications. It seems like /dev/urandom ought to be Good Enough. 15:45:18 hmm, as an application author, I'd be concerned that by reading from urandom all the time, I'm depleting the entropy pool for applications which need actual /dev/random. Is that a misguided line of thought? 15:45:30 I don't really know. 15:45:36 Or if it's too slow to use. 15:45:42 foom: it's much slower than, say, MT 15:45:55 It just *seems* like that would be a sensible way for things to work, not knowing anything about the subject at all. :) 15:45:57 and it doesn't provide repeatability. 15:46:12 nevermind antithetic variables and other niceties. 15:46:50 I don't know the actual history, but my guess is that /dev/urandom is there just to make sure that people don't misuse /dev/random just because it's convenient 15:47:04 pretty much. 15:47:25 The guarantee that it doesn't block is worth something. 15:47:26 Exhausting the entropy pool by abusing /dev/random would be pretty bad. 15:49:15 foom: sometimes, I wonder if there's something wrong with umontreal and we should just get our BSc and be unaware of these issues ;) 15:50:07 I thought /dev/random is for those security-conscious people who prefer not being able to log in to their servers at all when there's not enough entropy for fully secure authentication, whereas /dev/urandom is for people who prefer their servers to "work (almost securely)" instead of "not work (securely)". 15:50:18 pkhuong: Is there something in antithetic variables that makes them more difficult to generate from /dev/urandom than by other means? 15:50:31 leuler: not repeatable. 15:51:02 lack of probably independent sequence/subsequence also makes them pretty much useless. 15:51:24 interesting to know that FreeBSD doesn't actually distinguish between the two devices (if wikipedia is right). 15:51:47 -!- jdz [~jdz@193.206.22.97] has quit [Quit: Byebye.] 15:51:58 lichtblau: it just provides real randomness for both files? 15:52:18 the other way around IIUC 15:52:38 ok. I hope VIA users are peeved. 15:56:45 -!- slyrus_ [~chatzilla@99-28-161-110.lightspeed.miamfl.sbcglobal.net] has quit [Ping timeout: 256 seconds] 15:57:28 I guess /dev/random and /dev/urandom are the same thing on linux too, except that /dev/random decrements an arbitrary number that has almost no relation to anything. :) 16:02:01 foom: I distinctly remember 3 hours of lecture during which we deconstructed excel's, glibc's and java's PRNGs to show how much they suck. I've never trusted any system PRNG snce then ;) 16:02:21 slyrus_ [~chatzilla@adsl-67-116-253-131.dsl.pltn13.pacbell.net] has joined #sbcl 16:18:27 jdz [~jdz@host73-89-dynamic.54-82-r.retail.telecomitalia.it] has joined #sbcl 16:23:18 homie [~levgue@xdsl-87-79-192-231.netcologne.de] has joined #sbcl 16:25:40 -!- leuler [~user@p549036B0.dip.t-dialin.net] has quit [Quit: bbl] 16:44:48 -!- francisl [~flavoie@199.84.162.165] has quit [Remote host closed the connection] 16:45:08 francisl [~flavoie@199.84.164.114] has joined #sbcl 17:07:39 leuler [~user@p54901E5D.dip.t-dialin.net] has joined #sbcl 17:08:52 -!- jdz [~jdz@host73-89-dynamic.54-82-r.retail.telecomitalia.it] has quit [Quit: Byebye.] 17:12:00 -!- homie [~levgue@xdsl-87-79-192-231.netcologne.de] has quit [Quit: ERC Version 5.3 (IRC client for Emacs)] 17:16:48 borkman [~user@S0106001111de1fc8.cg.shawcable.net] has joined #sbcl 17:20:34 milanj [~milanj_@93-86-216-175.dynamic.isp.telekom.rs] has joined #sbcl 17:25:48 huangjs [~huangjs@190.8.100.83] has joined #sbcl 17:31:09 -!- slyrus_ [~chatzilla@adsl-67-116-253-131.dsl.pltn13.pacbell.net] has quit [Ping timeout: 252 seconds] 17:45:58 -!- gko [~gko@114-34-168-13.HINET-IP.hinet.net] has quit [Ping timeout: 244 seconds] 17:46:39 francisl_ [~flavoie@199.84.162.165] has joined #sbcl 17:47:58 -!- francisl [~flavoie@199.84.164.114] has quit [Read error: Operation timed out] 17:47:58 -!- francisl_ is now known as francisl 17:48:39 I'd like to get some feedback on two issues I noticed when changing the integer RANDOM code. The first one is loop rotation. See http://paste.lisp.org/display/129366 17:50:13 kanru` [~user@199.195.142.182] has joined #sbcl 17:50:47 It happens that the accept-reject loop compiled for this call to RANDOM is made worse by the loop rotation find-rotated-loop-head does. It does not consider loops that have the test at the end already. 17:51:53 -!- kanru` [~user@199.195.142.182] has quit [Remote host closed the connection] 17:52:15 kanru` [~user@199.195.142.182] has joined #sbcl 17:57:08 pkhuong: sounds like an ideal reason to use /dev/urandom, then! 17:57:27 antgreen [user@nat/redhat/x-wjifgwhbnkmemthd] has joined #sbcl 17:59:40 I can change that (see annotation 1), which I show to motivate the second issue: Now it happens more often that the NOPs used to align a loop start are not skipped by a jmp, but are executed. In the example there is only one, but on x86-64 there can be up to 15. Another example where NOPs are executed is when recursion into local functions is done. 18:00:44 So, I'd like to add "long nop"s to x86-64, that is, opcode 0f 1f. 18:01:25 I believe after some research that all existing processors capable of x86-64 support this opcode. 18:02:57 What do you folks think: Is this desirable, could it be enabled unconditionally on x86-64, or do we need *backend-subfeatures* here? 18:04:24 homie [~levgue@xdsl-87-79-192-231.netcologne.de] has joined #sbcl 18:07:10 blackwol` [~blackwolf@ool-4575fc51.dyn.optonline.net] has joined #sbcl 18:07:11 doesn't sound like a backend subfeature if it's true 18:07:27 and I guess we can define it as "true" if we don't get angry letters from some subset of x86-64 users 18:09:09 Well, I am sure enough that it's true to accept the accountability and commit the change. 18:10:27 sounds good to me 18:11:15 -!- blackwolf [~blackwolf@ool-4575fc51.dyn.optonline.net] has quit [Ping timeout: 260 seconds] 18:31:54 -!- angavrilov [~angavrilo@217.71.227.190] has quit [Read error: Operation timed out] 18:33:05 I need to think about where to put and how to activate a function that, given the number of alignment bytes to be filled with NOPs, emits a (sequence of) long NOPs of the correct length. 18:44:12 sdemarre [~serge@91.176.197.45] has joined #sbcl 18:49:34 -!- francisl [~flavoie@199.84.162.165] has quit [Quit: francisl] 18:51:44 LiamH [~none@pdp8.nrl.navy.mil] has joined #sbcl 19:12:04 -!- huangjs [~huangjs@190.8.100.83] has quit [Ping timeout: 272 seconds] 19:13:58 francisl [~flavoie@199.84.162.165] has joined #sbcl 19:17:05 huangjs [~huangjs@190.8.100.83] has joined #sbcl 19:19:05 nikodemus [~nikodemus@178-55-57-180.bb.dnainternet.fi] has joined #sbcl 19:19:05 -!- ChanServ has set mode +o nikodemus 19:20:43 nikodemus: regarding your comment about return-with-dynamic-extent 19:21:00 at ELS, I started off saying what you said (i.e. "wtf how are we meant to implement this?") 19:21:16 but then I remembered that we have %%NIP-VALUES, and suddenly I was less sure that we couldn't do it easily 19:22:25 -!- huangjs [~huangjs@190.8.100.83] has quit [Ping timeout: 260 seconds] 19:26:23 TimKack` [~user@c-2ec22154-74736162.cust.telenor.se] has joined #sbcl 19:26:31 is MOV memory to memory expensive? sbcl does the following dance MOV RSI, RAX; MOV RBX, RCX; MOV RBX, [RBX]; MOV [RSI], RBX 19:27:01 or is it just not possible? 19:27:14 -!- TimKack [~user@c-2ec22154-74736162.cust.telenor.se] has quit [Ping timeout: 245 seconds] 19:27:30 Kryztof: we may have %nip-values, but our stack analysis code has bugs already... 19:27:33 *stassats`* fires up the intel manual 19:28:08 and even then, i don't see how it could be efficient 19:28:57 no direct memory to memory moves aside from block copies on x86oids 19:29:06 MOV RBX, [RCX]; MOV [RAX], RBX would've been more sensible 19:29:33 no argument there :) 19:29:42 well, efficiency is relative. If the goal is to get efficiency by being completely non-(heap)-consing, then any consing is deadly, more deadly than shunting blocks of memory around the stack 19:29:49 any madeira-port love or hate? 19:29:54 "no problem, i'll write a VOP" 19:30:08 "in pursuit of microseconds" 19:30:34 Kryztof: true, but as i said, he can already write that function -- it just has to be inline 19:31:45 -!- TimKack` [~user@c-2ec22154-74736162.cust.telenor.se] has quit [Ping timeout: 260 seconds] 19:32:00 and given result-extent he can write the inline function body as (init-foo (alloc-foo)) where INIT-FOO can be out of line, so it doesn't even have to bloat code 19:32:54 now, having a declaration that says "inline if it allows you to use DX, don't bother otherwise" would be very neat. not sure if feasible, though 19:33:01 TimKack` [~user@c-2ec22154-74736162.cust.telenor.se] has joined #sbcl 19:34:56 nikodemus: I like it 19:37:09 slyrus_ [~chatzilla@173-228-44-92.dsl.static.sonic.net] has joined #sbcl 19:38:52 -!- jiacobucci [~jiacobucc@gw-asdl.ae.gatech.edu] has left #sbcl 19:41:59 nikodemus: it lacks an :version operator to test implementation version 19:42:58 fe[nl]ix: i couldn't think of a sane way to compare them, and equal comparison seems too brittle 19:43:14 suggestions welcome 19:44:44 typically, the version string format is stable, so it's not too difficult to extract a version vector from it 19:45:05 on sbcl "1.0.56" -> #(1 0 56) 19:45:53 on ccl "Version 1.9-dev-r15329M-trunk (LinuxX8664)" -> #(1 9 15329) 19:46:01 etc... 19:48:03 fe[nl]ix: that depends on implementation specific knowledge 19:48:25 nikodemus: This is a really dumb question I'm sure but...what does madeira-port offer via its component class that isn't available with plain reader conditionals? When would I use one over the other? 19:48:29 i /really/ don't want to try to keep up with all the different formats used 19:48:48 redline6561_: using a reader functional makes the defsystem harder to instrospect 19:48:52 introspect, even 19:49:10 for example, if you have tarball-op 19:49:17 ...ah, okay. 19:49:31 nikodemus: yes, inevitably 19:49:36 i also think it's easier on the eyes 19:49:48 I don't find myself introspecting quite that much but I think I see where you're going with that. And I *totally* agree that it is visually preferable. :) 19:50:04 but i won't blame if you choose to use the extended syntax in a .asd instead :) 19:50:53 but the syntax is mainly for non-asdf uses, in my mind, at least 19:50:59 yeah, feature-eval is cool hackery 19:51:11 yes, the real point is really the extended syntax 19:51:14 but I would be pretty nervous/uncomfortable using it in an ASD 19:51:26 nikodemus: unless we convince implementors to add a cl:*lisp-implementation* or similar, the only options are to rely on "implementation specific knowledge" or do nothing 19:51:27 Okay. Then that makes sense. Thanks! 19:51:47 huangjs [~huangjs@190.8.100.83] has joined #sbcl 19:51:58 redline6561_: i hope it was clear that :when and :unless support the extended syntax? 19:52:00 Also, fe[nl]ix +1. It is on github, nikodemus. Patches welcome if implementation version formats change and all that. 19:52:10 Yes. 19:52:40 i did think of adding :string>= and friends 19:52:57 nikodemus: is madeira-port even moderately stable ? I'd like to start using it right away 19:53:03 i suspect for most formats lexiographic comparison is almost good enough :) 19:53:48 fe[nl]ix: :madeira-port :when and :unless are expected to be 100% stable for plain feature tests 19:53:55 ok 19:54:12 the rest i'd say 98% stable unless someone points out that something is currently stupid 19:54:15 or broken 19:54:38 but i did mark it as 1.0 because i figured it was in usable shape 19:55:08 i'm still making a proper manual for it, but other than that i don't expect to be deprecating anything 19:55:23 which is also why i didn't go nuts with custom feature tests 19:56:31 i had at one point :find-special-operator-p, :find-method, :find-generic-function, :find-constant, etc, but decided that it's better to start a bit slimmer and add them later than regret and try to scale back 19:59:03 hm. i guess (:impl-version>= ...) could actually be supported sanely as a synonym for (:and :impl (:version>= ...)) -- but only implemented for those implementations who donate such comparisons 19:59:45 dekuked [~user@static-98-164-147-69.axsne.net] has joined #sbcl 20:00:37 nikodemus: ok, I'll add support for version>= 20:00:59 is a dependency on split-sequence fine for you ? 20:01:27 i'd rather not have any deps on it, purely out of ease-of-adoption motives 20:01:53 asdf itself probably has enough of a split function in it 20:01:58 split-sequence(and alexandria) are probably already on people's systems 20:02:02 true 20:02:17 Kryztof: good idea 20:02:19 hm, unrolling memory copying only slows me down 20:04:36 hahaha, asdf:split-string 20:05:25 i often find that split-sequence is not present 20:07:27 and it's even exported. interesting. 20:09:55 -!- specbot [~specbot@pppoe.178-66-37-60.dynamic.avangarddsl.ru] has quit [Disconnected by services] 20:09:58 -!- minion [~minion@pppoe.178-66-37-60.dynamic.avangarddsl.ru] has quit [Disconnected by services] 20:09:59 specbot [~specbot@pppoe.178-66-65-249.dynamic.avangarddsl.ru] has joined #sbcl 20:10:02 minion [~minion@pppoe.178-66-65-249.dynamic.avangarddsl.ru] has joined #sbcl 20:10:24 fe[nl]ix: apropos, it would be nice if cffi imported cffi-grovel-file &co into asdf, so the same :defsystem-depends-on trick would work for them (probably need to subclass with the cffi prefix for backwards compatibility and cleanliness, though...) 20:12:11 nikodemus: it does 20:12:53 at least in the git version 20:13:19 or something similar 20:13:22 -!- stassats` [~stassats@wikipedia/stassats] has quit [Ping timeout: 250 seconds] 20:13:39 I think I do a (setf (find-class) ...) instead of import 20:13:43 stassats [~stassats@wikipedia/stassats] has joined #sbcl 20:14:08 (setf (find-class 'asdf::cffi-grovel-file) (find-class 'grovel-file)) 20:16:17 ok, cool. missed that 20:16:21 --> good night 20:16:24 -!- nikodemus [~nikodemus@178-55-57-180.bb.dnainternet.fi] has quit [Quit: Leaving] 20:31:34 -!- francisl [~flavoie@199.84.162.165] has quit [Quit: francisl] 20:38:02 leuler: we've been needing long nops for quite a while. Intel's and AMD manuals have form up to 10ish bytes iirc. 20:38:45 pkhuong: does it make any difference? 20:38:52 stassats: hitting more than one memory location is always slow. 20:40:05 what do you mean? won't 10 bytes worth of ordinary nops be treated the same way? 20:40:36 sorry, the memory location was re mem-mem moves 20:40:56 anyway, yes, longer nops are fastter than a bunch of 0x90 20:41:13 they're decoded as a single, long, noop 20:41:47 so longer nop consume fewer resources. 20:41:58 is it noticeable? 20:42:03 pkhuong: nice to hear of the need. I looked at both company's guides and they differ slightly in their recommendations: AMD prefers to add a #x66 for some lengths while Intel prefers a lea there. After consulting Agner Fog's tables I think the #x66 works nice for both. 20:42:20 stassats: can be. 20:42:23 leuler: nice. 20:43:56 stassats: yes. For example the TAK benchmark gains 17 percent speed. That is a sequence of NOPs that is executed when calling a local function, so for each recursion step. 20:43:59 stassats: lots of uarchs have a decode limt of 3-4 instructions per cycle, for example. 20:44:18 -!- saschakb__ [~saschakb@p4FEA06B7.dip0.t-ipconnect.de] has quit [Read error: Connection timed out] 20:45:29 Unfortunately, the newest Intel architecture can decode long NOPs only at a rate of 1 per clock while #x90 at 4 per clock. Execution is 4 of each per clock. Older Intels can decode more long NOPs per cycle. 20:45:45 it would make sense to have backend options to optimize for different micro-architectures 20:46:19 I don't feel that we have the human resources for that. Better to try and target a robust meta-uarchitecture. 20:46:34 because clearly, hitting the common denominator will become harder and harder as time goes on 20:46:47 AMD decodes three #x90s cycle and needs no execution resources for them. Long NOPs it decodes three per cycle but I don't know at the moment whether they need execution resources. 20:46:50 we'll just deprecate performance targets as time goes. 20:47:25 leuler: so the general rule seems to be to have up to three 0x90, and then switch to long nops? 20:47:33 or drive more hackers to hack on sbcl 20:47:56 currently for this change I feel backend-specific adaptation is not necessary. Intel for one just says that the overriding rule for NOP optimization is to have the smallest possible number of instructions. 20:48:23 SHCL, Sanely Hackable Common lisp 20:48:41 -!- dekuked [~user@static-98-164-147-69.axsne.net] has quit [Read error: Connection reset by peer] 20:48:56 dekuked [~user@static-98-164-147-69.axsne.net] has joined #sbcl 20:48:58 leuler: sounds sane. 20:49:02 pkhuong: No, it begins #x90, #x66 #x90, #x0f #x1f #x00, ... 20:49:54 I believe SBCL code is often not decode constrained. 20:50:09 otoh, 4 nops in a row *is* decode constrained. 20:50:12 too much implicit knowledge is encoded into lower level parts, i still haven't got a hang of ir-transforms, code generation and gc 20:52:20 pkhuong: What I meant was, if a long sequence of instructions contains a short sequence of long NOPs I'd expect any decode limitation to be evened out. 20:52:22 leuler: I guess the best part is to detect when we emit alignment notes with 0x90 as the byte. Probably best to pass :nop instead and then generate long nops. Someone might want actual 0x90 in the future. 20:53:15 CampinSam [~Sam@24-176-98-217.dhcp.jcsn.tn.charter.com] has joined #sbcl 20:53:34 Also, with regard to the newest Intel above: The decode constraint for long NOPs is that they need the first of four decoders (which is responsible for several complex instruction types). The other three decoders are free to decode three more instructions in the same clock. 20:55:07 pkhuong: There is currently exactly one caller of alignment notes with #x90, that is in emit-block-header. x86-64 has other calls of emit-alignment, but all of them use the default of 0 for fill-byte. 20:58:18 As I said earlier today, I am still thinking about where to put the function that converts lengths to long NOP emission. emit-alignment is in src/compiler/assem.lisp and I don't like to put a machine-specific helper function in that file. Maybe I need to pass a function to emit-alignment instead or some data structure containing the byte sequences and information about the longest one. 20:59:37 Or is there a way to find whether there is and then call a backend-specific function from assem.lisp? 20:59:43 find out 21:08:31 -!- asedeno_work [~asedeno@74.125.59.113] has quit [Quit: *poof*] 21:15:59 francisl [~flavoie@199.84.164.114] has joined #sbcl 21:17:11 asedeno_work [~asedeno@74.125.59.113] has joined #sbcl 21:20:46 -!- homie [~levgue@xdsl-87-79-192-231.netcologne.de] has quit [Read error: Connection reset by peer] 21:25:10 francisl_ [~flavoie@199.84.162.165] has joined #sbcl 21:25:30 -!- sdemarre [~serge@91.176.197.45] has quit [Ping timeout: 260 seconds] 21:28:16 -!- francisl [~flavoie@199.84.164.114] has quit [Ping timeout: 252 seconds] 21:29:24 -!- francisl_ [~flavoie@199.84.162.165] has quit [Ping timeout: 256 seconds] 21:32:03 -!- antgreen [user@nat/redhat/x-wjifgwhbnkmemthd] has quit [Remote host closed the connection] 21:32:14 -!- CampinSam [~Sam@24-176-98-217.dhcp.jcsn.tn.charter.com] has quit [Quit: leaving] 21:32:50 dekuked` [~user@mail.kesnermorrissey.com] has joined #sbcl 21:36:08 -!- dekuked [~user@static-98-164-147-69.axsne.net] has quit [Ping timeout: 240 seconds] 21:50:08 homie [~levgue@xdsl-78-35-171-49.netcologne.de] has joined #sbcl 21:55:31 -!- dekuked` [~user@mail.kesnermorrissey.com] has quit [Ping timeout: 244 seconds] 22:02:45 -!- edgar-rft [~user@HSI-KBW-078-043-123-191.hsi4.kabel-badenwuerttemberg.de] has quit [Quit: ERC Version 5.3 (IRC client for Emacs)] 22:05:25 -!- joshee is now known as joshe 22:05:28 -!- psilord [~psilord@23-25-144-217-static.hfc.comcastbusiness.net] has quit [Quit: Leaving.] 22:07:31 saschakb [~saschakb@p4FEA0038.dip0.t-ipconnect.de] has joined #sbcl 22:12:05 -!- leuler [~user@p54901E5D.dip.t-dialin.net] has quit [Quit: ERC Version 5.1.2 $Revision: 1.796.2.6 $ (IRC client for Emacs)] 22:15:59 -!- saschakb [~saschakb@p4FEA0038.dip0.t-ipconnect.de] has quit [Ping timeout: 245 seconds] 22:17:34 francisl [~flavoie@bas1-montreal48-1176173836.dsl.bell.ca] has joined #sbcl 22:23:03 attila_lendvai [~attila_le@178-164-240-240.pool.digikabel.hu] has joined #sbcl 22:23:20 -!- attila_lendvai [~attila_le@178-164-240-240.pool.digikabel.hu] has quit [Changing host] 22:23:20 attila_lendvai [~attila_le@unaffiliated/attila-lendvai/x-3126965] has joined #sbcl 22:38:24 -!- attila_lendvai [~attila_le@unaffiliated/attila-lendvai/x-3126965] has quit [Ping timeout: 244 seconds] 22:52:08 attila_lendvai [~attila_le@188-143-57-21.pool.digikabel.hu] has joined #sbcl 22:52:08 -!- attila_lendvai [~attila_le@188-143-57-21.pool.digikabel.hu] has quit [Changing host] 22:52:08 attila_lendvai [~attila_le@unaffiliated/attila-lendvai/x-3126965] has joined #sbcl 22:59:30 -!- TimKack` [~user@c-2ec22154-74736162.cust.telenor.se] has quit [Remote host closed the connection] 23:03:00 TimKack [~tkack@c-2ec22154-74736162.cust.telenor.se] has joined #sbcl 23:03:01 tyson1 [~Ian@65.93.93.219] has joined #sbcl 23:03:26 -!- tyson1 [~Ian@65.93.93.219] has left #sbcl 23:03:51 -!- TimKack [~tkack@c-2ec22154-74736162.cust.telenor.se] has quit [Client Quit] 23:04:17 TimKack [~tkack@c-2ec22154-74736162.cust.telenor.se] has joined #sbcl 23:04:47 tyson1 [~Ian@65.93.93.219] has joined #sbcl 23:04:50 -!- tyson1 [~Ian@65.93.93.219] has left #sbcl 23:07:03 -!- LiamH [~none@pdp8.nrl.navy.mil] has quit [Quit: Leaving.] 23:30:22 -!- flip214 [~marek@unaffiliated/flip214] has quit [Excess Flood] 23:30:59 flip214 [~marek@unaffiliated/flip214] has joined #sbcl