tag:blogger.com,1999:blog-3946129347039216262.post8516458710305844664..comments2009-06-14T22:11:45.641-07:00Comments on random coding: Current Project:: Wait-Free Cache Allocator (pt 1)randomhttp://www.blogger.com/profile/14975312951134894629noreply@blogger.comBlogger4125tag:blogger.com,1999:blog-3946129347039216262.post-79733623514107828862009-06-14T22:11:45.641-07:002009-06-14T22:11:45.641-07:00Yeah, my worry with locality is that since the mem...Yeah, my worry with locality is that since the memory is allocated elsewhere I'll be getting cache hits a lot. Not on the data, as the data is never used, just the pointers. These are scattered around (somewhat... depending on what the new operator does) so that part is fairly unpredictable, thus "bad."<br /><br />The way I'm selecting tasks at the moment is pretty horrid too; I'm working on this now actually. Essentially, it boils down to a bunch of if/else's but I'm going to switch it to an atomic increment... but that might slow it down even more what with the underlying OS stuff to interrupt threads.<br /><br />The next post I'm putting up has the code in it, feel free to rip it apart. :)randomhttps://www.blogger.com/profile/14975312951134894629noreply@blogger.comtag:blogger.com,1999:blog-3946129347039216262.post-32361007983769483292009-06-14T14:41:21.650-07:002009-06-14T14:41:21.650-07:00Don't forget locality....
In the analogy, if ...Don't forget locality....<br /><br />In the analogy, if the worker has to put down his tools and pick up others (predictive caching has failed and new instructions have to be loaded) or walk over to the box machine (data not in the cache) then switching tasks picks up a lot more cost than if everything is local.John Trindlehttps://www.blogger.com/profile/14933356801960758686noreply@blogger.comtag:blogger.com,1999:blog-3946129347039216262.post-41968615260277167222009-06-12T20:29:06.945-07:002009-06-12T20:29:06.945-07:00hehe, I had to read the first sentence three times...hehe, I had to read the first sentence three times before I got it. :)<br /><br />You're right: Methods A and B assume that the machine can only be used by one person at a time. If someone else tries to use it, they go into a wait of some sort.<br /><br />Method C is a bit trickier to explain... each (except one) of the steps of making the boxes is totally discrete and parallelizable. When workers pack a box, they look for any available task and try to accomplish it.<br /><br />The packing analogy has issues here in that all but one of the steps can be done at the same time. Obviously, this isn't quite accurate with boxes... you can't clean up a mess you haven't made yet.<br /><br />The only step that forces everyone to wait is the part where the first person moves the new cardboard to the cutter (allocation.) Unluckily, this is the slowest part... Luckily, I fill this gap time using no-operation calls if needed.randomhttps://www.blogger.com/profile/14975312951134894629noreply@blogger.comtag:blogger.com,1999:blog-3946129347039216262.post-16907639427485788082009-06-12T12:54:23.473-07:002009-06-12T12:54:23.473-07:00Any initially empty boxes you leave unattended wil...Any initially empty boxes you leave unattended will immediately be occupied by N cats where N is approximately 1.<br /><br />I'm going to guess that a worker with an empty input queue and an empty workbench switches to making boxes, until his input queue is occupied by I >= IThresh units or I > 0 units for more than ITimeThresh time units, where he switches back to his workbench. If there is a worker already making boxes (the box machine is a constrained resource), the worker idles.<br /><br />If number boxes B > BThresh then every worker idles (since you have only BThresh cats to guard empty boxes).John Trindlehttps://www.blogger.com/profile/14933356801960758686noreply@blogger.com