#qi-hardware IRC log for Saturday, 2012-09-15

wpwrakquicksort moves a lot of things around. i don't need this. i can have this information in the code flow.00:00
mthwhat I described matches the "Partition-based general selection algorithm" section on that page00:02
wpwrakyeah. i basically want to unroll the thing.00:03
wpwraklike in the thee variables example. that one was small enough to keep in my head. i'm less optimistic about five ;-)00:04
mththe median of medians approach sounds useful00:04
mthyou could do that with groups of 3 as well, if your poor little CPU doesn't have many regs00:04
mthyou'd probably need special cases for sizes that are not powers of 300:05
mthtreating non-existing elements as infinity should be sufficient, I think00:05
mthah no, then you might not get the actual median00:06
mththe groups of 5 approach should work equally well for groups of 300:06
mthyou just have to do more passes then00:06
wpwrakhmm. maybe i should draw the thing. maybe 5 is still manageable with a clear head.00:07
wpwraksince all this shold be n log n ... let's see ... 3 -> 2*3 = 6. i have 5 comparisons, close enough :)00:09
mth5! = 120, so you can do an exhaustive test on the median-of-5-elements code00:09
wpwraknaw, it can't be worse than n log n00:10
wpwrakotherwise, i could just use quick- or heapsort00:10
mthI mean, you can just test all possible inputs and if your code passes it's ok00:10
wpwraksure. but that's excessive. even bubble sort would do better ;-)00:11
mthwell, maybe duplicate elements could be tricky, so you might need a bit more test cases, but still 5^5 is manageable00:11
mthjust for testing, not when actually running00:12
wpwrak5 log 5 is 11.6. so 12 is the goal :)00:12
mtheh, no-one said the constant was 1 ;)00:12
wpwrakah yes, for testing the algorithm, i'll just do something like n^n. that runs on the pc, so cycles are dirt cheap :)00:12
wpwrakit's all a question of picking the right unit of measure ;)00:13
mth12 decacompares :)00:14
wpwrakwell, 16 bit comparisons are already bad enough on an 8 bit mcu :)00:15
mthhmm, could you do something per bit?00:18
mthif you look just at the most significant bit and count the number of 0s and the number of 1s, the median will belong to the largest of those two groups00:19
wpwraksloooaawwwwly :) but probably per byte00:19
wpwrakactually, gcc may do that for me if it's smart about its data flow analysis and applies it to machine instructions and not the abstract 16 bit operations. not sure if it's that good, though.00:20
mthI mean a different algorithm, where you'd look at one bit at a time00:21
wpwrakhmm. that sounds O(n^2)-ish00:21
mthO(N * log R), where N is array length and R is range00:22
wpwrakbut yes, interesting approach if word operations are wordsize-times as expensive as bit operations00:22
wpwrakactually a bit faster00:23
wpwrakyou have N for the first bit. something in [N/2, N] for the second, etc.00:24
wpwrakwell, depends on how quickly you can filter our the ones you already know don't fit00:25
wpwrakshould be fun to implement in an FPGA :)00:25
mthis it allowed to shuffle elements around or should they stay at their starting indices?00:26
wpwraki think a copy is about as expensive as a compare. a swap twice that.00:27
wpwrakor maybe 1.5 times00:27
wpwrakso copying is expensive00:27
mthswap is the ideal operation for this kind of thing anyway00:28
wpwrakbut code is relatively cheap -> unrolling00:28
wpwraknaw, i need to select, not to reorder00:28
wpwrakof course, i could conceptually swap, without actually doing it00:28
wpwrake.g., if you say if (a < b) { swap(a, b); return something_else(a, b); }00:29
wpwrakthen one cuold simply if (a < b) return something_else(b, a);00:29
wpwrakthat's basically how you could read my 3 values example00:29
wpwrakthere is no copying/swapping there00:30
mthok, you swap variables, not array elements00:30
mthis it OK if the algorithm only works for odd-length arrays?00:41
wpwrakthat's fine, yes00:44
wpwrakavoids the pesky decision whether to pick v[(n-1)/2] or v[(n+1)/2] :)00:45
mthwpwrak: http://www.treewalker.org/temp/median-bitwise.py00:54
mthit figures out the value of the median one bit at a time00:57
wpwrakheh, pretty cool, yes00:57
wpwrakif you have an architecture where this is efficient, it's a very neat algorithm00:57
wpwraklower/higher don't seem to make sense, though (except for preventing you from running into the asser)01:02
mththey contain the number of elements below and above the range that matches the mask01:03
wpwrakah, right. you need that.01:03
mthusually I would add more comments, but it's 3 am here and the natural language part of my brain is half asleep01:04
wpwrakotherwise, the choice would be the most popular bits but not the median01:05
mthsomehow python is easier than English :)01:05
wpwrakoh, it's pretty much self-documenting :)01:05
mthyes, it has to pick the middle element of the entire array, not just of the examined subarray01:05
wpwrakbut .. 10 bits, 5 variables, and a relatively expensive inner loop .. that's something like a factor 10 more expensive than what whould be possible with a compare and branch approach01:06
mthit's simple and not hugely inefficient, but it might not be the best solution for you01:08
wpwrakyeah, i'm afraid it'll be a pencil and paper exercise. first the tree, then balancing it ...01:09
Aylalarsc, hi14:34
AylaI'd like to extend your ohci-jz4740 driver to other JZ devices14:35
Aylamind if I just rename "jz4740" to just "jz" on the filename and the code?14:35
larscAyla: usually that's not done, just use the driver as is for the other devices14:44
Aylaso I just copy-paste the code?14:45
larsckeep it as it is and extend it where necessary14:46
larscbut don't rename everything14:46
xiangfu@tweet QEMU emulated Ben NanoNote http://youtu.be/q6BxbAtJ7F415:18
whitequarkwhy qi-bot talks hiragana?!15:32
larscwhy not?15:37
qi-bot[commit] Mark Brown: ASoC: core: Try to use regmap if the driver doesn't set up any I/O (jz-3.5) http://qi-hw.com/p/qi-kernel/90ff12517:20
qi-bot[commit] Mark Brown: ASoC: core: Fix check before defaulting to regmap (jz-3.5) http://qi-hw.com/p/qi-kernel/82a40fe17:20
qi-bot[commit] Mark Brown: ASoC: io: Use dev_get_regmap() if driver doesn't provide a regmap (jz-3.5) http://qi-hw.com/p/qi-kernel/c21575f17:20
qi-bot[commit] Lars-Peter Clausen: ASoC: jz4740: Use regmap (jz-3.5) http://qi-hw.com/p/qi-kernel/d8b0b5c17:20
GCW2012anyone with knowledge about ITE IT6610 HDMI21:18
GCW2012or Vivante GC860 GPU21:19
--- Sun Sep 16 201200:00

Generated by irclog2html.py 2.9.2 by Marius Gedminas - find it at mg.pov.lt!