On Thursday, January 28, 2016 at 11:36:50 PM UTC-6, Brandon Thomas wrote: > On Thu, 2016-01-28 at 20:32 -0800, Scotty C wrote: > > > I think you understand perfectly. > > i'm coming around > > > > > You said the keys are 128-bit (16 byte) values. You can store one > > > key > > > directly in a byte string of length 16. > > yup > > > > > So instead of using a vector of pointers to individual byte > > > strings, > > > you would allocate a single byte string of length > > > {buckets x chain length x 16} > > > and index it directly as if it were a 3-dimensional array [using > > > offset calculations as you would in C]. > > i'm going to actually run my code later (probably in the morning). > > and then grab some stats from the hash. take a look at the stats. > > give me some thoughts on the above implementation after looking at > > the stats. > > > > > Can you explain why the bignums are important. For a simple task > > > like > > > filtering a file, they would seem to be both a waste of memory and > > > a > > > performance drain wrt storing the key values as byte strings. > > ok, true story. about 10 years ago i'm a student taking an intro to > > ai class we have been assigned the 3x3 tile puzzle and 2 algorithms, > > ida* and a*. also, try it on a 4x4. so i whip these out and am > > appalled by how slow the fn things are but intrigued by what they can > > do and i'm just a puzzle kind of guy. btw, the 4x4 wasn't solvable by > > my stuff at the time. so i head to the chief's office with my little > > bit of code. tell him it's way to slow. what do you think? he takes 5 > > seconds to peruse the item and says "you're probably making too much > > memory". side note, later i graded this class for that prof and the > > same project. not a single student, including the ms and phd types, > > did anything better than a vector of vectors of ints. so back to me, > > i'm thinking, how do i cram 4 bits together so that there is > > absolutely no wasted space. i start digging through the documentation > > and i find the bitwise stuff. i see arithmetic shift and having no > > idea whether it will work or not i type into the interface > > (arithmetic-shift 1 1000000). if we blow up, well we blow up big but > > we didn't. i flipped everything in my project to bignum at that > > point. the bignum stuff is massively faster than vector of vectors of > > ints and faster than just a single vector of ints. lots of bignum is > > easy to implement, like the hash. making a child state, not so much. > > i'm not married to bignums despite all this. > > > > > I've been programming for over 30 years, professionally for 23. > > i was a programmer. dot com bought us as a brick and mortar back in > > '99 and the whole shebang blew up 2 years later. idiots. anyway, been > > a stay at home dad for the most part since then. > > > > > have an MS in Computer Science > > me too. that's the other piece of the most part from up above. > > > > > (current-memory-use) > > yup, tried that a while back didn't like what i saw. check this out: > > > > > (current-memory-use) > > 581753864 > > > (current-memory-use) > > 586242568 > > > (current-memory-use) > > 591181736 > > > (current-memory-use) > > 595527064 > > > > does that work for you? > > > > For whatever you're storing, I still suggest using a disk based > structure (preferably using one that's already optimised and built for > you). I've done a bit of work on cache aware algortihms, where reducing > memory footprint is really big (along with the memory juggling). Yes, > if you try to store something that takes only a few bits and store each > one into an integer, you'll have waisted space. In theory, you could > use a bignum, and only shift it as many bits as you need, which is what > you have done. The issue with that is that bignum's have extra overhead > thats neccessary for it to do arithmetic. Obviously, there needs to be > a way to match or beat bignums with primitive structures, since bignums > are implemented with primitive structures. So, if you want to beat > bignum for storage, you'll want to use some contiguous memory with > fixed sized elements (like byte strings, or arrays of uint32_t's in C) > - but using bit manipulation on each byte, such that you have multiple > stored values in each one, directly beside eachother bitwise, like a > bignum has, but without it's overhead. > > Regards, > Brandon Thomas
-- You received this message because you are subscribed to the Google Groups "Racket Users" group. To unsubscribe from this group and stop receiving emails from it, send an email to racket-users+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.