Index

Show enters and exits. Hide enters and exits.

02:16:30evanbrixen: I can't understand the existing qsort code, so I recoded it to help me understand it. http://gist.github.com/396835
06:19:44brixenevan: awesome, and your recoded version fails to have the bug that I showed earlier
06:19:53evanthats correct.
06:19:53brixenunderstandable and correct
06:19:54brixenwin
06:19:55brixen:)
06:20:10evanpasses the sort specs we have
06:20:15brixenexcellent
06:20:18evannot sure how extensive they are
06:20:21brixenI'll add this case
06:20:35brixenapparently, tim sort is in jdk 7
06:20:42brixenmight be interesting to investigate
06:20:46evanok
06:20:49evanpost 1.0 perhaps
06:20:51brixenyep
06:20:57evanmy qsort is ported from the qsort wikipedia page.
06:21:00brixenare you going to push this?
06:21:06evanif you'd like me to
06:21:12brixenI don't see why not
06:21:16evani still wonder what the heck is going on in the existing qsort
06:21:23brixenlet's see, do we have some benches
06:21:29evanperhaps
06:21:32brixenmight be good to do a sanity check on perf
06:22:58brixenthe existing sort is a three-way qsort
06:23:13brixendunno if it was a lot more performant than a regular qsort
06:24:33evanwell
06:24:54evanlooking at the description of three-way qsort helps see what the current qsort is doing
06:24:59evanbut i suspect it's also the source of the bug.
06:25:15evansince it attempts to treat values that are equal to the pivot specially
06:25:33evanwhich is one big property of the broken sorted array
06:25:50evangiven the complexity involved
06:25:57evanthe sorter algorithm might be faster
06:26:19evaneven if it's does more comparisons
06:26:22evanin my qsort
06:26:35evanI ignore elements that are equal to the pivot, not moving them
06:26:44evannot sure if thats a bug or not, but that minimizes some operations
06:26:45slavahi evan
06:26:48slavaqsort eh
06:26:50slavawhy not mergesort?
06:27:01evani was trying to fix the existing one
06:27:15evanand i'm trying to do minimize the changes
06:27:22evansince we're in 1.0 lockdown.
06:27:27brixenI think the simple qsort is fine
06:27:54brixenyes, the equal key treatment in 3-way is very likely the cause of this bug
06:28:03brixenI'm reading the algo now
06:28:03scooprnot moving equal elements would mean it's "stable", right?
06:28:20brixenscoopr: not necessarily
06:28:47evanscoopr: no, because the pivot is always moved around
06:29:17scooproh right, pivot
06:29:39evanbrixen: well, i'm going to actually head to bed here
06:29:45evanyou wanna check it over
06:29:54evanand go ahead and commit it if you're happy with it/
06:29:54evan?
06:30:28brixenI'll wait till morning
06:30:32brixenI'm still looking at this
06:30:33evank
06:30:38evancheck it over
06:30:39brixenk
06:30:41evanand lets discuss in the morning.
06:30:44brixensounds good
06:30:51slavado you have a roadmap for after 1.0?
06:31:02brixenslava: more like a freeway map :D
06:31:09evanslava: we're starting to put one together.
06:33:07evanok, good night!
06:35:15brixennight!
16:13:23evanmorning.
16:13:56brixenmorning
16:14:20brixenso, the reimplemented sort is slightly slower on the benchmark/rubinius/standalone_array_sort.rb
16:14:30brixenbut not enough to worry I think
16:14:43brixenI could reimplement the 3-way partition algo
16:14:54brixenor we could run with this for 1.0
16:16:19evanhm.
16:16:22evanlets go with the simple one
16:16:28evani'm worried about making too big of a change.
16:16:46evaneven replacing the method whole sale is a little worrysome
16:16:54evanbut I don't have a better way to deal with this bug.
16:16:57brixenindeed
16:17:30evanthe code in those benchmarks is pretty pathalogical
16:17:40evani'm betting that most real world usages of sort will be the same.
16:17:50brixenright
16:18:23brixenhave you run the rails 3 tests with this?
16:18:31evanno, but I can.
16:18:39brixenok
16:36:31evanhm, got a hang.
16:37:45evanin spin_lock
16:38:19brixenhm
16:40:06evanmmm
16:40:07evanok
16:40:10evanit's in the kill specs
16:40:14evanthat this is happening.
16:45:35evanok, i think I see the spin_lock deadlock problem.
16:45:56brixensweet
16:49:04evan:/
16:49:20evanpthread_cond_signal is not safe to use from a signal handler.
17:03:56evanif anyone is curious, here is the case: http://gist.github.com/397548
17:05:51brixenhmm
17:08:28scoopreww, threads + signals + cross-platform vm that needs to make sense of it all.. have fun! =)
17:41:11evanwell hrmph
17:41:21evani think the best is to work around this by not using a Channel for sleeping
17:42:32brixencould we use a Tent or SleepingBag? :)
17:43:07evanheh
22:31:31imajesevan: hey, does/can/will rbx support ++ and -- operators?
22:31:38imajesit'd be nice to have that sugar to get around foo = foo +1
22:31:43evannever.
22:31:56evanthats what += 1 is for.
22:32:22imajessadness.
22:32:28brixenimajes: you should search the mailing list for the N discussions of adding += 1
22:32:41imajeshaha
22:32:51brixenyes, the sadness is that N would likely be a Bignum on most platforms
22:32:51imajes+= 1 is nicer for sure.
22:33:06brixener, adding ++
22:33:54brixenand by mailing list, I mean MRI mailing lists like ruby-core
22:33:55evanimajes: no one will add it
22:34:00evanunless they're making their own language.
22:34:04imajessure,
22:34:05evanie, not-ruby.
22:34:43imajesright
22:34:52imajesbut += is rbx? i don't think i remember getting mri tosupport it
22:35:22slavaevan: when is rbx going to support postfix syntax
22:35:25slavaand static types
22:35:48evanwhen I add inline COBOL
22:36:32evanCOBOL do
22:36:34evan IDENTIFICATION DIVISION.
22:36:36evan PROGRAM-ID. HELLO-WORLD.
22:36:38evan PROCEDURE DIVISION.
22:36:40evan DISPLAY 'Hello, world'.
22:36:42evan STOP RUN.
22:36:44evanend
23:16:03evanbrixen: trying to replace sleep with something that uses nanosleep is causing more trouble
23:16:06evanso i'm not going to do that.
23:17:47brixenok
23:18:16evanthere is a lot of thread interaction
23:18:33evanit's going to require some extensive testing to do differently, I think.
23:18:37brixenok
23:18:51evani'll try and come up with another workaround to avoid the spin_lock deadlock
23:18:52brixenthreads and signals are just the cat's meow huh
23:18:56evanno
23:18:57evanthey're not.
23:19:07brixen</sarcasm> :)
23:19:12evan:)
23:36:39evanfunny, apple added qsort_b()
23:36:48evanwhich takes a block instead of a function pointer
23:37:16evanFUCKING A RAILS.
23:37:29brixen:/
23:37:46brixenevan: logged into IM?
23:37:51evanyep.
23:37:56brixenhum
23:38:13brixenshows you as offline
23:38:41evanaim is fucked up I think.