5 ms·

I haven’t really encountered a loop that there isn’t a function for. There ought to be some exhaustive list of all the different kinds of loops in computer scie

I haven’t really encountered a loop that there isn’t a function for. There ought to be some exhaustive list of all the different kinds of loops in computer science textbook. But Most of what you need is in Zip, fold, map, reduce, filter, find, sort, reverse, transpose, permute, concat, any, all, max, min, cycle, take, .. I’ve periodically done microbenchmarks of inner loops over the years and the various gcc outputs of the c++ loop functions are always performing slightly better than if I hand rolled. Perhaps with gcc7 or clang this is different.

jstimpfle 8y ago
> Zip, fold, map, reduce, filter, sort, reverse, transpose, permute, concat, any, all, max, min, cycle, take, .. Cool, so if that's all we should just use those. But wait, what about those dozens of megabytes of data, should we really zip/transpose/concat them? We should use non-strict evaluation then...
- tuukkah 8y ago
  You can use lazy lists / streams even with strict evaluation, you just have to be explicit.
  - jstimpfle 8y ago
    Point being, I'd rather not have this complexity. Do you mean to explicitly take each next value from the stream? And then possibly throwing all this "lazy" work away? Or memoizing the work and writing extra code that checks if the work was already done when the data is accessed? And then probably forgetting to get rid of the data when it's no longer needed? No thanks, that's even worse. It's honest, but that doesn't make it a good idea. I like to do one thing at a time, not jump around like a wild horse. Turns out optimizing for not jumping around too much also makes programs simpler overall. I've recently cleaned up some code of this kind. Defines objects with unsuitable lifetime and tries to be smart about reusing work instead of planning out in which order to do things in the first place. While the actual task was not difficult, the code was incomprehensible, to state it in a diplomatic way.
    - xfer 8y ago
      Not sure where you get all this idea of complexity from, lazy streams are used in functional languages a lot for data processing and they are not incomprehensible, also imperative languages like rust has iterators that are more used than for/while loops.
      - jstimpfle 8y ago
        Well, I described the situations from which I get my ideas of complexity... Regarding iterators, I'm fine with their usage depending on what they _do_. However I don't think it's a good idea to iterate over an abstract stream that under the hood does sorts and zips and folds. Because you lose control and understanding how much intermediate data will be produced (constant small amount? 3 times the amount?), and in what order code gets executed. And if you think consciously about the intermediate data you probably can use it for a whole lot of other things! In Haskell, unexpected memory expansions and duplication of work can happen. And these problems are not nice to debug. I might be generalizing too much, though. Maybe you're talking about short-lived web applications that never see a large amount of data, or something like that.
    - tuukkah 8y ago
      For example, streams without complexity in Java: https://docs.oracle.com/javase/8/docs/api/java/util/stream/package-summary.html https://docs.oracle.com/javase/8/docs/api/java/util/stream/p...
jstimpfle 8y ago
> I’ve periodically done microbenchmarks of inner loops over the years and the various gcc outputs of the c++ loop functions are always performing slightly better than if I hand rolled. Perhaps with gcc7 or clang this is different. Any code examples? What I was thinking of is hand-rolling for (a; b; c;) BODY to a; loop: if (!b) goto out; BODY c; goto loop; out: ...
- goalieca 8y ago
  My thought about hand rolling is that any loop is hand-rolled if I tell the compiler how to do things (ie not declarative). Writing out a for loop with an s+=*p++ for summing the elements in a vector is hand rolling a “reduce”. You can add all the tricks you want like changing the stride, doing simd, prefetching, but I’ve learned to let the compiler or the math/data library do its job. For small data (MB) the compiler or library can parallelize things nicely. Bigger data (TB+) can be chewed threw by using MPI aware libraries that optimize and schedule and everything. Database work is already declarative because SQL is just so awesome. C# and java now handle fusion and streams more nicely and c++ can in-line and r-value a lot of overhead away.
  - deleted 8y ago
    [deleted]
  - jstimpfle 8y ago
    Yeah you need to be careful what kind of iteration you do. Modifying pointers is likely problematic. Iterating over a range of integers on the other hand should be easy to optimize. In most cases, it shouldn't matter and it's much more important to think about the data accesses, due to the relative slowness of memory.
setr 8y ago
One situation I haven't found a good construct for yet is iterating over a list to do some work unrelated to the list ie foreach(i in list){ if i == 0 { class.a() } else { class.b() } }
- goalieca 8y ago
  But foreach is a function. The weird thing about your pattern is that class.a() and class.b() may have side effects and don’t seem to depend on i at all. If I were to optimize this loop or even make it parallel, then I’m certainly missing some information. Some information that could be captured by another expression.

jstimpfle 8y ago

> Zip, fold, map, reduce, filter, sort, reverse, transpose, permute, concat, any, all, max, min, cycle, take, .. Cool, so if that's all we should just use those. But wait, what about those dozens of megabytes of data, should we really zip/transpose/concat them? We should use non-strict evaluation then...

tuukkah 8y ago
You can use lazy lists / streams even with strict evaluation, you just have to be explicit.
- jstimpfle 8y ago
  Point being, I'd rather not have this complexity. Do you mean to explicitly take each next value from the stream? And then possibly throwing all this "lazy" work away? Or memoizing the work and writing extra code that checks if the work was already done when the data is accessed? And then probably forgetting to get rid of the data when it's no longer needed? No thanks, that's even worse. It's honest, but that doesn't make it a good idea. I like to do one thing at a time, not jump around like a wild horse. Turns out optimizing for not jumping around too much also makes programs simpler overall. I've recently cleaned up some code of this kind. Defines objects with unsuitable lifetime and tries to be smart about reusing work instead of planning out in which order to do things in the first place. While the actual task was not difficult, the code was incomprehensible, to state it in a diplomatic way.
  - xfer 8y ago
    Not sure where you get all this idea of complexity from, lazy streams are used in functional languages a lot for data processing and they are not incomprehensible, also imperative languages like rust has iterators that are more used than for/while loops.
    - jstimpfle 8y ago
      Well, I described the situations from which I get my ideas of complexity... Regarding iterators, I'm fine with their usage depending on what they _do_. However I don't think it's a good idea to iterate over an abstract stream that under the hood does sorts and zips and folds. Because you lose control and understanding how much intermediate data will be produced (constant small amount? 3 times the amount?), and in what order code gets executed. And if you think consciously about the intermediate data you probably can use it for a whole lot of other things! In Haskell, unexpected memory expansions and duplication of work can happen. And these problems are not nice to debug. I might be generalizing too much, though. Maybe you're talking about short-lived web applications that never see a large amount of data, or something like that.
  - tuukkah 8y ago
    For example, streams without complexity in Java: https://docs.oracle.com/javase/8/docs/api/java/util/stream/package-summary.html https://docs.oracle.com/javase/8/docs/api/java/util/stream/p...

jstimpfle 8y ago

> I’ve periodically done microbenchmarks of inner loops over the years and the various gcc outputs of the c++ loop functions are always performing slightly better than if I hand rolled. Perhaps with gcc7 or clang this is different. Any code examples? What I was thinking of is hand-rolling for (a; b; c;) BODY to a; loop: if (!b) goto out; BODY c; goto loop; out: ...

goalieca 8y ago
My thought about hand rolling is that any loop is hand-rolled if I tell the compiler how to do things (ie not declarative). Writing out a for loop with an s+=*p++ for summing the elements in a vector is hand rolling a “reduce”. You can add all the tricks you want like changing the stride, doing simd, prefetching, but I’ve learned to let the compiler or the math/data library do its job. For small data (MB) the compiler or library can parallelize things nicely. Bigger data (TB+) can be chewed threw by using MPI aware libraries that optimize and schedule and everything. Database work is already declarative because SQL is just so awesome. C# and java now handle fusion and streams more nicely and c++ can in-line and r-value a lot of overhead away.
- deleted 8y ago
  [deleted]
- jstimpfle 8y ago
  Yeah you need to be careful what kind of iteration you do. Modifying pointers is likely problematic. Iterating over a range of integers on the other hand should be easy to optimize. In most cases, it shouldn't matter and it's much more important to think about the data accesses, due to the relative slowness of memory.

setr 8y ago

One situation I haven't found a good construct for yet is iterating over a list to do some work unrelated to the list ie foreach(i in list){ if i == 0 { class.a() } else { class.b() } }

goalieca 8y ago
But foreach is a function. The weird thing about your pattern is that class.a() and class.b() may have side effects and don’t seem to depend on i at all. If I were to optimize this loop or even make it parallel, then I’m certainly missing some information. Some information that could be captured by another expression.