7 ms·

Cache behavior simulation would be kind of a pain to implement, but I might give it a shot at some point. What is branch behavior? I'm not familiar with the t

Cache behavior simulation would be kind of a pain to implement, but I might give it a shot at some point. What is branch behavior? I'm not familiar with the term.

pbiggar 15y ago
Yeah, I can see that. A big problem is that the set sizes where cache effects start to come into effect are much larger than the sizes you're modelling. A level 1 cache is going to have 4K, which is at least 5x the size you're modelling by default. But you can probably use play sizes, like a cache which only holds 16 or 32 ints. By branch behaviour, I mean branch prediction. I did some research (http://paulbiggar.com/research/#sorting-tr http://paulbiggar.com/research/#sorting-tr) before that showed that branch prediction is really important for sorts. For example, insertion sort is way better than selection sort, and radix sort has really really good branch prediction properties, making it beat quicksort (well, this is LSB radixsort, and I think you implemented MSB radixsort, but no doubt it applies somewhat). So for the branch simulation, implement a 2 bit dynamic saturating counter, and note the number of mispredictions. There are simpler and more complex predictors, but that's probably the simplest that's a reasonable approximation of real life.
- thedufer 15y ago
  I'll definitely implement a cache model to show cache behavior. I'm not sure branch prediction is realistic, though; I'm not actually parsing the code myself, so finding the branch points would be a lot of extra work. I'm considering a scheme where you have to call an extra function inside each branching statement to get useful branch prediction results. Something along the lines of: for x in foreach([1...VA.length], "for1") y = 0 while branch(VA.gt(x, y), "while1") y++ if branch(y == x, "if1") break VA.insert(x, y) Where the `branch`, `foreach` functions are identities over their first argument, and they use the second argument to to track branching for a given branch point (i.e. you must uniquely name each branch, foreach line). A foreach would be a branch run arg0.length + 1 times, with arg0.length true branches followed by a single false branch. Sound at all reasonable?

Cache behavior simulation would be kind of a pain to implement, but I might give it a shot at some point. What is branch behavior? I'm not familiar with the term.

pbiggar 15y ago

Yeah, I can see that. A big problem is that the set sizes where cache effects start to come into effect are much larger than the sizes you're modelling. A level 1 cache is going to have 4K, which is at least 5x the size you're modelling by default. But you can probably use play sizes, like a cache which only holds 16 or 32 ints. By branch behaviour, I mean branch prediction. I did some research (http://paulbiggar.com/research/#sorting-tr http://paulbiggar.com/research/#sorting-tr) before that showed that branch prediction is really important for sorts. For example, insertion sort is way better than selection sort, and radix sort has really really good branch prediction properties, making it beat quicksort (well, this is LSB radixsort, and I think you implemented MSB radixsort, but no doubt it applies somewhat). So for the branch simulation, implement a 2 bit dynamic saturating counter, and note the number of mispredictions. There are simpler and more complex predictors, but that's probably the simplest that's a reasonable approximation of real life.

thedufer 15y ago
I'll definitely implement a cache model to show cache behavior. I'm not sure branch prediction is realistic, though; I'm not actually parsing the code myself, so finding the branch points would be a lot of extra work. I'm considering a scheme where you have to call an extra function inside each branching statement to get useful branch prediction results. Something along the lines of: for x in foreach([1...VA.length], "for1") y = 0 while branch(VA.gt(x, y), "while1") y++ if branch(y == x, "if1") break VA.insert(x, y) Where the `branch`, `foreach` functions are identities over their first argument, and they use the second argument to to track branching for a given branch point (i.e. you must uniquely name each branch, foreach line). A foreach would be a branch run arg0.length + 1 times, with arg0.length true branches followed by a single false branch. Sound at all reasonable?