2013-10-21T01:54:17 *** MegaAlex|away has quit IRC (Ping timeout: 272 seconds) 2013-10-21T01:57:02 *** MegaAlex|away has joined #rtems 2013-10-21T02:08:44 *** sebhub has joined #rtems 2013-10-21T02:09:12 good morning 2013-10-21T02:12:29 *** kiwichris has joined #rtems 2013-10-21T02:24:45 sebhub, hi 2013-10-21T02:26:21 hi chris, just look at the microblaze error 2013-10-21T02:26:52 Great. I think I have most things building except the microblaze and v850. 2013-10-21T02:26:57 This is for 4.8.2 2013-10-21T02:27:21 I am building with the latest newlib 2013-10-21T02:28:04 these types are defined in "newlib/libc/sys/rtems/machine/_types.h" 2013-10-21T02:37:50 microblaze doesn't use the rtems target includes 2013-10-21T02:40:06 there is no "targ-include" directory in the build tree 2013-10-21T02:43:56 I am not sure what this means. What do I need to add to fix it ? 2013-10-21T02:44:11 i have no idea currently 2013-10-21T02:44:41 Oh ok. I will ping Joel. He will be on planes all day tomorrow. 2013-10-21T02:45:46 The microblaze suffers from a change in config.hosts in libgcc where microblaze-*-* was changed to microblaze-*-elf (or something) which broke RTEMS 2013-10-21T02:46:19 I wonder if there are other places, such as newlib where a similar change broken it 2013-10-21T02:48:03 hm, yes, microblaze has no libgcc config! 2013-10-21T02:48:29 I have a patch for that. The _mode_t error came after that. 2013-10-21T02:48:53 can you send me this patch please 2013-10-21T02:48:59 yeap 2013-10-21T02:50:33 http://www.rtems.org/ftp/pub/rtems/people/chrisj/rtems-gcc-microblaze-libgcc-20131017.diff 2013-10-21T02:53:44 these copy and paste GCC configs are very bad in the long run (I mean config.gcc for rtems*-*-rtems*) 2013-10-21T02:54:26 Yes. The split libgcc has been a mess 2013-10-21T02:55:22 no I mean somthing else, the rtems config part is usually only a slightly different elf/eabi/newlib config 2013-10-21T02:56:05 if we place our stuff in this area, people have to take us into consideration, if we use our own copy and paste block, then things regularly break 2013-10-21T02:57:03 Yes. Joel would have liked comments to manage the wildcard results. 2013-10-21T02:57:29 This was a wild card to something specific. 2013-10-21T02:57:42 i moved for example the arm config into the general arm elf section 2013-10-21T02:57:57 with an 'or' for rtems ? 2013-10-21T02:58:05 yes 2013-10-21T02:58:21 I agree with this. 2013-10-21T02:58:33 The microblaze patch does the same. 2013-10-21T02:58:48 yes, this is good 2013-10-21T02:59:03 the bad thing is ralfs config.gcc copy and paste block 2013-10-21T02:59:33 Ah ok. I have not looked closely. Maybe this should be cleaned up. 2013-10-21T03:00:20 I am off for the evening and then travelling for a day or so. 2013-10-21T03:02:02 *** kiwichris has quit IRC (Quit: This computer has gone to sleep) 2013-10-21T08:21:37 *** MegaAlex|away has quit IRC (Ping timeout: 272 seconds) 2013-10-21T08:23:04 *** MegaAlex|away has joined #rtems 2013-10-21T09:30:29 *** kiwichris has joined #rtems 2013-10-21T09:36:21 *** sebhub has quit IRC (Ping timeout: 240 seconds) 2013-10-21T11:07:13 *** vipulnayyar has joined #rtems 2013-10-21T11:26:35 *** vipulnayyar has quit IRC (Ping timeout: 248 seconds) 2013-10-21T11:30:56 *** kiwichris has quit IRC (Quit: This computer has gone to sleep) 2013-10-21T12:00:05 *** vipulnayyar has joined #rtems 2013-10-21T12:06:02 *** vipulnayyar has quit IRC (Quit: Leaving) 2013-10-21T12:26:05 *** kiwichris has joined #rtems 2013-10-21T12:37:24 *** kiwichris has quit IRC (Quit: This computer has gone to sleep) 2013-10-21T14:19:43 *** antgreen has quit IRC (Ping timeout: 272 seconds) 2013-10-21T14:34:01 *** antgreen has joined #rtems 2013-10-21T14:45:02 *** antgreen has quit IRC (Ping timeout: 240 seconds) 2013-10-21T14:57:55 *** antgreen has joined #rtems 2013-10-21T19:46:42 *** kiwichris has joined #rtems 2013-10-21T21:18:13 *** kiwichris has quit IRC (Quit: This computer has gone to sleep) 2013-10-21T21:29:26 *** kiwichris has joined #rtems 2013-10-21T21:58:03 *** kiwichris_ has joined #rtems 2013-10-21T21:59:46 *** kiwichris has quit IRC (Ping timeout: 245 seconds) 2013-10-21T23:39:29 *** kiwichris_ has quit IRC (Quit: This computer has gone to sleep) 2013-10-22T01:32:30 *** MegaAlex|away has quit IRC (Ping timeout: 245 seconds) 2013-10-22T01:33:20 *** MegaAlex|away has joined #rtems 2013-10-22T01:46:07 *** sebhub has joined #rtems 2013-10-22T02:03:56 good morning 2013-10-22T03:04:26 *** MegaAlex|away has quit IRC (Ping timeout: 264 seconds) 2013-10-22T03:05:00 *** MegaAlex|away has joined #rtems 2013-10-22T06:32:23 *** MegaAlex|away has quit IRC (Ping timeout: 260 seconds) 2013-10-22T06:33:08 *** MegaAlex|away has joined #rtems 2013-10-22T08:49:27 *** MegaAlex|away has quit IRC (Ping timeout: 251 seconds) 2013-10-22T08:50:09 *** MegaAlex|away has joined #rtems 2013-10-22T10:32:37 *** sebhub has quit IRC (Remote host closed the connection) 2013-10-22T11:09:16 *** vipulnayyar has joined #rtems 2013-10-22T11:28:24 *** vipulnayyar has quit IRC (Quit: Leaving) 2013-10-22T15:24:09 *** edwardk has joined #rtems 2013-10-22T15:32:05 *** xMYTHICx has joined #rtems 2013-10-22T15:32:43 *** xMYTHICx has quit IRC (Client Quit) 2013-10-22T15:32:57 *** xMYTHICx has joined #rtems 2013-10-22T23:32:15 *** antgreen has quit IRC (Read error: Connection reset by peer) 2013-10-22T23:32:46 *** antgreen has joined #rtems 2013-10-22T23:45:29 *** kiwichris has joined #rtems 2013-10-23T02:22:51 *** sebhub has joined #rtems 2013-10-23T02:23:00 good morning 2013-10-23T03:05:20 *** kiwichri_ has joined #rtems 2013-10-23T03:07:15 *** kiwichris has quit IRC (Ping timeout: 272 seconds) 2013-10-23T03:14:12 sebhub, what do you think about me adding a POSIX Init task as a default that calls the ctors and then main ? 2013-10-23T03:51:04 i would keep it as is, if a user adds more than one init task, then its his problem 2013-10-23T03:51:30 we just have to do something to prevent that idle threads call the static ctors 2013-10-23T03:52:11 adding more than one init thread is the same as starting threads from static ctors 2013-10-23T04:11:51 on the other hand i think the concept of init tasks is questionable, it adds no real value and makes things more complicated 2013-10-23T04:17:49 I think the ctor code in thread place it is is a hack and should be moved 2013-10-23T04:18:28 RTEMS Init tasks are not standard and yet are the default while RTEMS prompts itself as following standards 2013-10-23T04:18:40 prompts -> promotes 2013-10-23T04:19:13 the init tasks are also confusing, people know what main() is, but init tasks... 2013-10-23T06:57:47 *** antgreen has quit IRC (Ping timeout: 272 seconds) 2013-10-23T09:33:50 *** edwardk has quit IRC (Quit: Computer has gone to sleep.) 2013-10-23T09:37:00 *** edwardk has joined #rtems 2013-10-23T10:07:27 *** edwardk has quit IRC (Quit: Computer has gone to sleep.) 2013-10-23T10:55:26 *** sebhub has quit IRC (Remote host closed the connection) 2013-10-23T12:35:14 *** edwardk has joined #rtems 2013-10-23T13:56:28 hya 2013-10-23T13:56:32 hey 2013-10-23T13:56:48 you were asking about succinct indexed dictionaries and wavelet trees? 2013-10-23T13:56:56 i was just relaying what you said to me for chris 2013-10-23T13:57:13 he feels it could be useful for RFS (RTEMS File System) 2013-10-23T13:57:57 too bad gedare isn't here 2013-10-23T13:57:59 edwardk, hi 2013-10-23T13:58:02 it is a shame we didn't get to talk about my whole wavelet tree stack, there is a connection to the work that has been done for use the use of stratified doubling arrays / cache oblivious lookahead arrays in more recent filesystems. 2013-10-23T13:58:26 we'd have needed another whole day for that topic, i think 2013-10-23T13:58:55 i have an admittedly rather daunting paper list providing references for my analytics project at https://github.com/analytics/analytics/blob/master/notes/papers.md 2013-10-23T13:59:09 that gives a lot of references for the kinds of data structures i use 2013-10-23T13:59:34 i need to update it for the references that hav come out n the last few months, including poppy, my current preferred succinct indexed dictionary 2013-10-23T13:59:54 heya kiwichri_. nice to associate a nick with a name and face =) 2013-10-23T14:00:09 yeah same 2013-10-23T14:00:39 i presume the channel is logged, so if we talk about it then he'd be able to pick up the pieces? 2013-10-23T14:00:44 that's an interesting set of papers, i've read several of them 2013-10-23T14:00:47 edwardk: yep it's logged 2013-10-23T14:01:14 http://www.rtems.org/irclogs/index.html 2013-10-23T14:01:16 yeah, given that paper list you can kind of triangulate what the analytics project is about. =) 2013-10-23T14:01:30 chris has to go in 10 mins to play tennis, after he does that and finishes up after his inevitable trip to the hospital he'll be back 2013-10-23T14:01:39 fair enough 2013-10-23T14:01:58 ah the price of being old ... and now fat after all the beer and food 2013-10-23T14:02:10 i came back weighing less than when i left 2013-10-23T14:02:16 i was dissapointed 2013-10-23T14:02:19 hah 2013-10-23T14:02:34 see you can drink beer more than once a year 2013-10-23T14:02:42 i came back with a few extra pounds of fish in my gullet 2013-10-23T14:03:17 heh not surprised 2013-10-23T14:03:22 my wife, who is running a half-marathon this weekend, tsk tsk'd when i told her the story 2013-10-23T14:03:32 haha 2013-10-23T14:03:45 i do that once or twice a week (half marathon) 2013-10-23T14:03:51 planning on doing that tonight, actually 2013-10-23T14:03:51 haha 2013-10-23T14:04:10 no you Amar 2013-10-23T14:04:15 great for thinking 2013-10-23T14:04:18 i can't bring myself to do it to my knees. maybe when i get my weight down closer to yours it'd be viable. i'll stick to walking 2013-10-23T14:04:34 that's a great plan 2013-10-23T14:05:00 i use the walk in/out from work to think, read papers, etc. 2013-10-23T14:05:01 My legs also fall apart if I run. 2013-10-23T14:05:31 edwardk: for me running can be fairly mindless sometimes i'll run and not even realise how far i've gone while thinking about a topic.. that's what my gps watch is for 2013-10-23T14:06:09 *** DrJoel has joined #rtems 2013-10-23T14:06:09 *** DrJoel has joined #rtems 2013-10-23T14:06:09 *** ChanServ sets mode: +o DrJoel 2013-10-23T14:06:19 I heard there was a disturbance in here. 2013-10-23T14:06:30 it did lead to a bit of an imbalance though, before i had a very productive balance between researching ahead of myself and implementing behind. when i started walking to/from work every day i found the imbalance led to me iterating through papers far faster so my ideas outpaced my executions pretty badly for a while. now i try to mix up the papers with various communication tasks, so that i keep 'just the right distance' ahead of my 2013-10-23T14:06:31 implementations 2013-10-23T14:06:33 heya DrJoel 2013-10-23T14:06:49 Haskel Hooligans.. Perl Mongers.. : 2013-10-23T14:06:54 Hey Edward.. 2013-10-23T14:07:21 i figured i'd come in here and disrupt your nice little community. i figured it was a fair exchange for luring verm__ into #haskell/#haskell-lens ;) 2013-10-23T14:07:57 hah 2013-10-23T14:08:07 maybe he'll talk me into implementing realtime haskell or something ;) 2013-10-23T14:08:10 my lab is a few degrees warmer from compiling now 2013-10-23T14:08:48 DrJoel: we were talking about http://en.wikipedia.org/wiki/Succinct_data_structure that i queried in the email 2013-10-23T14:09:00 edward said he's not ware of patent issues and chris belives it could be useful for RFS 2013-10-23T14:09:34 Awesome! 2013-10-23T14:09:36 the principal researchers in the space are all academics, and are very geographically distributed. 2013-10-23T14:09:53 the common approaches are so obvious it'd be hard to patent anything 2013-10-23T14:11:02 e.g. rank-9 is a way to implement 'rank', and it consists of the ever so complicated step of breaking the vector up into 64 bit words and storing a prefix sum so that to calculate rank you shift off to find the position, lookup the prefix sum and add the masked popcount 2013-10-23T14:11:51 poppy adds a secondary level to it, at your scales you don't even need that because i doubt you'll be doing much that needs to exceed 2^32 vector size wise, otherwise you can use full poppy which works for vectors out to 2^64 in length for 3% overhead or so 2013-10-23T14:12:06 the code is already in c and fits in a few screens 2013-10-23T14:13:54 is the code up somewhere? 2013-10-23T14:14:12 looking for the c version, one sec. 2013-10-23T14:14:47 Nice 2013-10-23T14:16:33 once you have a basic rank/select structure adding a wavelet tree on top is trivial 2013-10-23T14:16:43 making it extensible is something i've done a lot of as well 2013-10-23T14:16:51 there we lean on other tools though 2013-10-23T14:17:09 i was just about to ask that 2013-10-23T14:17:17 http://www.cs.cmu.edu/~dga/papers/zhou-sea2013.pdf 2013-10-23T14:17:33 that is the paper for poppy 2013-10-23T14:18:27 let me get the code 2013-10-23T14:18:54 Did I miss the "big-O" 2013-10-23T14:19:01 order of the algorithm? 2013-10-23T14:19:16 back shortly, meeting 2013-10-23T14:19:20 O(1) 2013-10-23T14:19:29 Thanks.. 2013-10-23T14:19:33 O(1) rank O(log n) select 2013-10-23T14:19:42 there are O(1) select algorithms but the constants are worse 2013-10-23T14:20:40 Lovely!!! O(constant) is a nice property for us at run-time. But O(log n) is acceptable especially if the N can be bounded by a design factor like maximum priorities or blocks in a file or something. 2013-10-23T14:21:13 mind you this is O(1) to basically popcount bits in a bitvector up to a given point 2013-10-23T14:21:19 its a way to prefix sum bits 2013-10-23T14:21:26 then a wavelet tree turns that into a structure that lets you do more 2013-10-23T14:21:50 with that i can do things like compute efficient medians, full text index, inverted index, etc. 2013-10-23T14:22:28 if you want a good overview of the space of algorithms that are possible with wavelet trees then id recommend first reading some other paper to get an idea of how wavelet trees work, then going back and reading a summary paper by navarro. one sec. 2013-10-23T14:23:27 http://www.dcc.uchile.cl/~gnavarro/ps/cpm12.pdf gives a comprehensive set of algorithms that it can be used for 2013-10-23T14:24:18 I love this side-effect of GSOC! The cross-pollination is absolutely amazing. 2013-10-23T14:25:00 basically a wavelet tree is a way to 'power up' rank and select algorithms from working on a simpler alphabet (0 or 1) n this case, to one that can work on prefix-free codes made out of that simpler alphabet, e.g. huffman codes, chars as fixed length codes, etc. 2013-10-23T14:25:20 this is most of what i spent the conference running around explaining to folks. 2013-10-23T14:25:31 I had been drinking too much when you got to me. :( 2013-10-23T14:25:59 i've been slowly building up a full fledged database in haskell using these techniques. i was forced into them largely by the fact that the world of databases are a patent minefield 2013-10-23T14:26:12 this let me sidestep everything i know about 2013-10-23T14:26:49 actually here, i can show how a wavelet tree works by walking you through doing an operation on the image on wikipedia: http://en.wikipedia.org/wiki/Wavelet_Tree 2013-10-23T14:26:56 see the image on the right? 2013-10-23T14:27:56 we'll use 'rank', which is defined as rank_a(S,i) = the # of occurrences of a in S[0..i), rank_1(S,i) is the prefix sum of how many 1s you have up to a given position. 2013-10-23T14:28:46 now lets say you have the string abracadabra and you want to know how many occurences you have of 'c' in the string up to position 5. in that tree, c is coded as 10 2013-10-23T14:29:46 so start at the top of the tree and compute rank_1(00101010010, 5) = 2, and then chain from that result to compute rank_0(1011, 2) this says you have 1 'c' in the first 5 characters of 'abracadabra' 2013-10-23T14:30:08 back later 2013-10-23T14:30:20 unfortunately same here.. have meeting now 2013-10-23T14:30:27 you can compute the position of the nth element by walking up the tree, etc. 2013-10-23T14:30:39 but the storage can be made succinct 2013-10-23T14:30:47 i'll catch up when folks have time =) 2013-10-23T14:31:50 but you can use this to maintain an indexed sequence of strings in compressed space using succinct encodings for the bit vectors such that you can still efficiently access them 2013-10-23T14:31:59 hopefully soon! Algorithmic improvements in Chris' RTEMS Filesystem are important and eventually WILL be in space. 2013-10-23T14:32:34 there are other tools in my toolbox that are just now getting to be used for file system work as well 2013-10-23T14:33:01 http://arxiv.org/pdf/1103.4282.pdf 2013-10-23T14:33:22 that is particularly useful if you need persistence/rollback for your filesystem 2013-10-23T14:33:31 and is very easily implemented 2013-10-23T14:33:59 the bloom filter variant they mention is similar to one i use in my in-memory COLA and can be quite fast 2013-10-23T14:34:28 f you're willing to degrade to O(log^2 n) for some operations you can even do without in sufficiently constraint memory applications 2013-10-23T14:34:35 giving you a knob to tune for space vs speed 2013-10-23T14:35:28 Cool! We are always open to algorithm improvements. One area of particular interest is how to efficiently manage sets of time triggered events. Right now, we use a list which is a sorted delta chain 2013-10-23T14:36:39 which means an event being inserted out of order is an O(n) hit? 2013-10-23T14:37:49 or do they never get inserted out of order? 2013-10-23T14:38:42 the amusing thing about having spent so much time talking to each other at gsoc over the years is that i read everything in your respective voices =P 2013-10-23T14:39:43 Yep. :( 2013-10-23T14:40:21 This structure is augmented by a wheel in *BSD as I recall but that just gives you an division by the number of wheels whichi still sucks 2013-10-23T14:40:40 I actually do the same thing on voices. LOL 2013-10-23T14:41:27 One big issue in that events that are to trigger need to come off during the clock tick and that has to be very efficient 2013-10-23T14:41:40 the implementation of poppy can be found here: https://github.com/efficient/rankselect 2013-10-23T14:41:43 we are also looking at one set per CPU and/or scheduler cluster 2013-10-23T14:42:15 that gives rank with good constants and consistent space overhead. 2013-10-23T14:42:43 https://github.com/simongog/sdsl-lite provides a bunch of other reference implementations for succinct data structures 2013-10-23T14:43:06 the papers for those are all linked in that markdown doc i gave above 2013-10-23T14:43:15 *** gedare has joined #rtems 2013-10-23T14:43:32 i have a lot of this in haskell, but that just makes it harder for you to read ;) 2013-10-23T14:43:44 did i miss the fun? *reading back the logger* 2013-10-23T14:43:56 gedare; you missed the intro and me throwing out reading lists ;) 2013-10-23T14:44:37 ok. i've been ignored by the logger for 5 minutes, so i'll read what i managed to scrape up. 2013-10-23T14:45:31 ignored bt the logger? 2013-10-23T14:45:51 12 commands in 1 minute = ignore 2013-10-23T14:46:08 makes it terribly hard to read the log efficientily 2013-10-23T14:47:14 who set it up to do that...i'll remove it when it migrates 2013-10-23T14:47:31 http://paste.lisp.org/display/139588 2013-10-23T14:47:42 heh thanks that's easier to read too! 2013-10-23T14:49:19 i have a video i'm posting up about the cola stuff soon, and i have to come up with a talk topic for a talk in budapest in a couple of weeks, so i may do wavelet trees 2013-10-23T14:49:42 not sure what kind of urgency you have 2013-10-23T14:49:46 it's interesting. 2013-10-23T14:49:56 pfft, things around here move glacially 2013-10-23T14:50:29 hey.. winter is coming.. :) 2013-10-23T14:50:31 But there is also global warming 2013-10-23T14:51:10 "Winter is coming"? 2013-10-23T14:51:11 ;) 2013-10-23T14:53:42 anyways, if anyone wants a crash course, i spend an awful lot of time walking to/from work so i can do a pretty in depth voice / google hangout chat on it some time 2013-10-23T14:54:19 that sounds useful 2013-10-23T14:54:43 getting everyone online at the same time can be tricky, inevitably someone it's 11pm for one person, 2pm for one and 4am for another 2013-10-23T14:55:07 reminiscent of union-find type structures, and also radix trees 2013-10-23T14:55:43 and prefix trees. 2013-10-23T14:55:54 well, in theory if we did it via google hangout you can tell it to record the session as a video for later 2013-10-23T14:56:23 that way if someone can't make it they can get the video and go through 2013-10-23T14:57:00 we did that for a workshop on my libraries back in march. i hopped on remotely and we recorded the whole thing via google hangout 2013-10-23T14:57:54 We want to do that more. Chris set up an RTEMS Project account just for us to have a channel and do that 2013-10-23T15:01:45 gedare: yeah, the way i like to think of a wavelet tree is it is a mapping between data in some arbitrary order and putting it in order by some prefix free code. if you choose an order preserving prefix free code you even preserve locality during the translation 2013-10-23T15:02:01 then the storage space of the tree can be tied directly to the amount of entropy in the permutation it represents 2013-10-23T15:02:21 so if you have two sorts that are almost the same, then the wavelet tree to convert between them is very small 2013-10-23T15:02:28 at least using RM or RRR 2013-10-23T15:02:39 (using poppy/rank-9 its basically the same size) 2013-10-23T15:03:04 RM and RRR are two other implementation techniques for succinct indexed dictionaries, just the basic rank/select structure on bitvectors) 2013-10-23T15:03:42 ok 2013-10-23T15:03:45 what i wind up doing with this stuff is using a compression scheme to get a prefix free code i want to use, then use that to store my data 2013-10-23T15:03:56 but the size of the wavelet tree is largely independent of that code 2013-10-23T15:04:47 the reason i use it has to do with when i want to pick an order that i can put my data in that i can sort it by several criteria and have low 'permutation entropy' when converting to any of those orderings 2013-10-23T15:05:11 e.g. the stuff you've seen here is all about one index, which is probably sufficient to your needs. 2013-10-23T15:05:36 i'm not a consumer so much. i like data structures, though. ;) 2013-10-23T15:05:38 in my case i'm doing things like storing data with multiple key components that i may want to aggregate by, join on, etc. 2013-10-23T15:05:54 well, by 'your needs' i mean 'file system needs' 2013-10-23T15:06:02 right i got that from the context 2013-10-23T15:06:54 why i care about this is i can throw something like a petabyte of data at it, and as my data set gets bigger my indexing set gets proportionally smaller 2013-10-23T15:07:50 e.g. a succinct dictionary is defined in terms of 0th order entropy. if you have a bit vector with k of n bits set, then there are (n choose k) such bit vectors so you could store the choice in log (n choose k) (+ 1) bits 2013-10-23T15:09:07 H_0 = log (n choose k) + 1 is the 0th order entropy. you're using no local features of the bitvector to help compress. e.g. you don't have the conditional probabilities that if the previous symbol was 1 the next symbol would be 1 with x% probability, etc. 2013-10-23T15:09:18 0th order = 0 bits of context 2013-10-23T15:09:34 a succinct dictionary is one that can be represented in H_0 + o(H_0) space 2013-10-23T15:09:51 in practice if H_0 = n then the o term is like n / log n 2013-10-23T15:10:08 so at a gig its something like 1/30th of a gig, at a terabyte, 1/40th of a terabyte, etc. 2013-10-23T15:10:23 so at peta-scale the overhead is quite nice 2013-10-23T15:10:44 and even in the small its nothing to sneeze at 2013-10-23T15:10:46 ahh 2013-10-23T15:11:34 the storage space is often smaller than the bit vector you started with when the vector is sufficiently skewed towards 1s or 0s, and contains the information from the original vector 2013-10-23T15:11:59 now, i use compression schemes for my data, so in practice i'm almost always at k ~ n / 2 so i don't get the compression wins there, but i get them from other means 2013-10-23T15:12:34 via the original compression, which is less good, but fairer when i'm doing complex indexing 2013-10-23T15:14:34 does it really matter whether a wavelet tree is used, or another form of digital trie can substitute for the "indexing" structure? 2013-10-23T15:14:59 it seems the primary gain is in the efficiency (storage and compute-wise) of rank 2013-10-23T15:15:00 what you need is a prefix free code. the wavelet tree itself is just a way to make a 'dependent bit index' 2013-10-23T15:15:05 i see. 2013-10-23T15:15:13 you don't need it to be balanced 2013-10-23T15:15:27 navarro i think defines it in terms of a balanced full wavelet tree 2013-10-23T15:15:30 but thats bunk 2013-10-23T15:15:36 you can use any shape 2013-10-23T15:15:56 it may depend on the other operations done on the tree. 2013-10-23T15:16:03 yeah 2013-10-23T15:16:16 now, you can abuse rank/select to encode the tree itself very succinctly as well 2013-10-23T15:16:23 this is something you may not have seen before 2013-10-23T15:16:29 are you familiar with DFUDS encoding? 2013-10-23T15:16:32 no 2013-10-23T15:16:43 ok, lets just play with rank/select for a minute 2013-10-23T15:17:33 it turns out that just using a bitvector and rank/select you can encode a tree in 2n + o(n) bits per node by using balanced parentheses encoded as 0s and 1s for ( and ), with O(1) access to the immediate children, parens, the corresponding closing parens. 2013-10-23T15:18:20 the naive encoding of it is to just treat 'entering the node as an opening paren, and leaving it as a closing paren (()()) represents a tree with two children 2013-10-23T15:18:33 this is the BP or balanced parentheses representation 2013-10-23T15:18:43 ok 2013-10-23T15:19:13 you can navigate a node down to its kth child in log k time, and to the corresponding paren to the one you are at in O(1), up to your parent in O(1), etc. 2013-10-23T15:19:19 quite ingenious and very packed 2013-10-23T15:19:27 but we can improve child access 2013-10-23T15:20:23 the child accesses can be sped up to O(1) instead of O(log k), even in the presence of huge numbers of children, by switching the encoding of a node to be k opening parens for a node with k children, followed by one closing paren 2013-10-23T15:20:34 each node is referenced by the ( in its parent, and by its own ), so we have almost a balanced tree 2013-10-23T15:20:40 we just need a ( before the root 2013-10-23T15:20:48 and you now have a balanced set of parens 2013-10-23T15:21:01 now you can play games with rank/select and get O(1) child access as well 2013-10-23T15:21:39 (there is another encoding called LOUDS, which is useful if you need a breadth first index, but don't need certain other ops, etc.) 2013-10-23T15:21:54 these are useful for encoding any kind of tree structure in very little space 2013-10-23T15:22:12 explicit pointer models take a full pointer, here 2 bits is a lot smaller than any pointer you'll ever find ;) 2013-10-23T15:22:22 and you can still navigate through the tree in O(1) 2013-10-23T15:22:29 and its the same thing you need for everything else 2013-10-23T15:22:59 http://www.df.lth.se/~jj/Publications/ultra_succinct_tr4_JCSS_2012.pdf 2013-10-23T15:23:39 how do you get from the node to the data? 2013-10-23T15:23:42 http://www.siam.org/proceedings/soda/2010/SODA10_013_sadakanek.pdf 2013-10-23T15:23:43 lets work through that. =) 2013-10-23T15:23:46 brb need water, brain cells starving. 2013-10-23T15:23:49 we can borrow from the idea of a wavelet tree 2013-10-23T15:24:35 ok 2013-10-23T15:25:01 we can have one bit vector that describes how to interleave 'shape' and 'data' , a set of balanced parens for the shape, and a bit array of contiguously written data for your nodes 2013-10-23T15:25:27 this is what i'm building for a persistent data model in haskell, where i only pay to lazily deserialize the portion of the structures i look at into haskell ADTs 2013-10-23T15:25:39 in something like rtems you'd need to be more explicit 2013-10-23T15:26:25 http://www.di.unipi.it/~ottavian/files/semi_index_cikm.pdf describes a related construction for json that i'm using a lot these days 2013-10-23T15:27:04 basically instead of parsing json, which tends to inflate it by a factor of 20, build an index that is about 5-10% of the size of the original document, and answer queries by mixing the index with the original document text. 2013-10-23T15:27:32 got it 2013-10-23T15:27:35 not much json on a rover or something i hope, but the idea is the same for binary data 2013-10-23T15:27:53 there its not self terminating so the coding is slightly different 2013-10-23T15:30:22 say you wanted to serialize a tuple (1,[2,3]) you could represent that as ((1)(cons(2)(cons(3)(nil)))) -- where cons and nil are tags like 0 or 1 for the indices of the constructors in the list data type. 2013-10-23T15:31:09 so you'd get ((1)(1(2)(1(3)(0)))) where i take that and split it first using a bitvector to say what is () and what is data first 2013-10-23T15:31:28 using 0 for parens: 00100101001010010000 2013-10-23T15:31:35 and then data: 112130 2013-10-23T15:31:53 interesting 2013-10-23T15:31:56 btw DrJoel in linux the timers use red-black tress now i believe. 2013-10-23T15:31:57 and the raw shape vector: (()(()(()()))) 2013-10-23T15:32:22 now you can deserialize only the portions of that tree you care about 2013-10-23T15:33:02 i see 2013-10-23T15:33:20 it costs a lot to update? 2013-10-23T15:33:27 have to recreate / rewrite the bit vectors 2013-10-23T15:33:32 shifting bits, etc? 2013-10-23T15:33:34 this assumes an immutable tree for this part 2013-10-23T15:33:38 right, ok 2013-10-23T15:33:44 oh, haskell.. 2013-10-23T15:33:55 its also being used as a serialization format 2013-10-23T15:33:57 just make a new tree and forget the old one exists eventually ;) 2013-10-23T15:34:12 so this is the artifact on disk 2013-10-23T15:34:16 ah, 2013-10-23T15:34:57 i collect ways to make data structures succinct/compact -- which is kind of hilarious given that the average executable I build is several megabytes ;) 2013-10-23T15:35:21 very different than when i cared about anything remotely embedded 2013-10-23T15:36:16 heh. 2013-10-23T15:36:38 bbiab 2013-10-23T15:37:27 thanks for the intro course. i shall be looking at these structures some more. i'd like to get a sense of where they "shine" and where they are not quite up to snuff. 2013-10-23T15:37:50 did you catch his list of papers at the start of the conversation? 2013-10-23T15:40:19 yeah 2013-10-23T15:40:34 i've read half the material on his github papers.md page too before. 2013-10-23T15:40:55 i have not come across the succinct data structures before though. it is interesting. 2013-10-23T16:02:44 back 2013-10-23T16:03:28 heading out for the night. thanks though! 2013-10-23T16:03:32 *** gedare has quit IRC (Quit: Leaving) 2013-10-23T16:03:52 later 2013-10-23T16:04:48 yes thanks for the in depth review that was fantastic 2013-10-23T16:05:15 np 2013-10-23T16:05:29 i'm happy to clear up any ambiguity as needed, mostly trying to give folks intuition 2013-10-23T16:05:45 since its easy to read papers once you know what they are for 2013-10-23T16:06:01 right 2013-10-23T16:07:03 and this is at least the sort of thing i don't have to bury someone in haskell up to their neck before they can grok it. 2013-10-23T16:14:40 *** edwardk has quit IRC (Read error: Connection reset by peer) 2013-10-23T16:19:12 *** DrJoel has quit IRC (Quit: Oops. My brain just hit a bad sector) 2013-10-23T16:23:29 yeah i hear that, ramp up time can amount to a lot 2013-10-23T18:48:50 *** edwardk has joined #rtems 2013-10-23T19:37:50 *** edwardk has quit IRC (Quit: Computer has gone to sleep.) 2013-10-23T20:01:12 *** edwardk has joined #rtems 2013-10-23T22:54:08 *** edwardk has quit IRC (Quit: Computer has gone to sleep.) 2013-10-23T23:00:39 *** mkhoory has joined #rtems 2013-10-23T23:20:22 *** mkhoory has joined #rtems 2013-10-24T01:48:10 *** sebhub has joined #rtems 2013-10-24T01:57:14 good morning 2013-10-24T03:47:22 *** sebhub has quit IRC (Remote host closed the connection) 2013-10-24T03:48:10 *** sebhub has joined #rtems 2013-10-24T05:13:12 *** antgreen has joined #rtems 2013-10-24T05:42:22 *** mkhoory has quit IRC (Read error: Connection reset by peer) 2013-10-24T06:56:26 *** antgreen has quit IRC (Ping timeout: 245 seconds) 2013-10-24T07:55:25 *** MegaAlex|away has quit IRC (Ping timeout: 245 seconds) 2013-10-24T07:58:56 *** MegaAlex|away has joined #rtems 2013-10-24T08:08:19 *** MegaAlex|away has quit IRC (Ping timeout: 260 seconds) 2013-10-24T08:08:56 *** MegaAlex|away has joined #rtems 2013-10-24T08:20:24 *** antgreen has joined #rtems 2013-10-24T08:31:39 *** sebhub has quit IRC (Ping timeout: 252 seconds) 2013-10-24T10:10:08 *** MegaAlex|away has quit IRC (Ping timeout: 265 seconds) 2013-10-24T10:16:08 *** MegaAlex|away has joined #rtems 2013-10-24T10:54:46 *** MegaAlex|away has quit IRC (Ping timeout: 245 seconds) 2013-10-24T11:13:02 *** edwardk has joined #rtems 2013-10-24T11:18:59 *** edwardk has quit IRC (Quit: Computer has gone to sleep.) 2013-10-24T11:41:11 *** vipulnayyar has joined #rtems 2013-10-24T11:44:53 *** MegaAlex|away has joined #rtems 2013-10-24T11:54:30 *** vipulnayyar has quit IRC (Quit: Leaving) 2013-10-24T12:16:34 *** antgreen has quit IRC (Ping timeout: 268 seconds) 2013-10-24T12:30:18 *** antgreen has joined #rtems 2013-10-24T14:23:05 *** edwardk has joined #rtems 2013-10-24T15:00:48 *** antgreen has quit IRC (Quit: Leaving) 2013-10-24T16:43:33 *** edwardk has quit IRC (Read error: Connection reset by peer) 2013-10-24T17:18:29 *** antgreen has joined #rtems 2013-10-24T18:14:57 *** edwardk has joined #rtems 2013-10-24T18:39:11 *** antgreen has quit IRC (Ping timeout: 260 seconds) 2013-10-24T20:27:04 *** edwardk