2 ms·

languages with side-effects cannot be automatically parallelized without changing the semantics and introducing observable nondeterminism Considering I spent y

languages with side-effects cannot be automatically parallelized without changing the semantics and introducing observable nondeterminism Considering I spent years working on automatic parallelizing compilers for Fortran and C++, I'd say it is possible. I don't know why you consider the heavily computational kernels of C programs less interesting just because they don't have side effects or make IO calls. For instance I worked on some algorithms to parallelize linked-list traversals, something that you would normally think is by definition serial.

mbrubeck 17y ago
I didn't say that side-effect-free program kernels are "less interesting" - I said they were beside the point of this post. (But I do think they're very cool and important in their own right!) The GHC developers' point was that restricted side effects are necessary for automatic parallelization. Your answer seems to be, "I can parallelize languages with unrestricted side-effects... in sections where you restrict yourself to a side-effect-free subset." Yes, I'm happy when a C++ compiler automatically optimizes my inner loop. But I'd rather be able to use "par" at the highest level of my program, and parallelize anything from XML parsing to physics simulation, without worrying that some library call ten functions down the stack will turn out to be non-reentrant.
astine 17y ago
Could you share the algorithm (or a link)? I'm very interested.
- codexon 17y ago
  http://software.intel.com/en-us/blogs/2007/12/20/linked-lists-incompatible-with-parallel-programming/ http://software.intel.com/en-us/blogs/2007/12/20/linked-list... "Traversing a linked list is inherently serial. [Theorists will point out that traversal can be done in parallel if you have a processor per node in the list. Feel free to buy that many Intel processors -- I own Intel stock.]" One possible implementation would be to use a skip list where you have each core search each level.

mbrubeck 17y ago

I didn't say that side-effect-free program kernels are "less interesting" - I said they were beside the point of this post. (But I do think they're very cool and important in their own right!) The GHC developers' point was that restricted side effects are necessary for automatic parallelization. Your answer seems to be, "I can parallelize languages with unrestricted side-effects... in sections where you restrict yourself to a side-effect-free subset." Yes, I'm happy when a C++ compiler automatically optimizes my inner loop. But I'd rather be able to use "par" at the highest level of my program, and parallelize anything from XML parsing to physics simulation, without worrying that some library call ten functions down the stack will turn out to be non-reentrant.

astine 17y ago

Could you share the algorithm (or a link)? I'm very interested.

codexon 17y ago
http://software.intel.com/en-us/blogs/2007/12/20/linked-lists-incompatible-with-parallel-programming/ http://software.intel.com/en-us/blogs/2007/12/20/linked-list... "Traversing a linked list is inherently serial. [Theorists will point out that traversal can be done in parallel if you have a processor per node in the list. Feel free to buy that many Intel processors -- I own Intel stock.]" One possible implementation would be to use a skip list where you have each core search each level.