4 ms·

My understanding is that all three of these algorithms MD5, SHA1, and RC4 are inherently difficult to parallelize. The result cannot be computed by splitting th

My understanding is that all three of these algorithms MD5, SHA1, and RC4 are inherently difficult to parallelize. The result cannot be computed by splitting the input, processing the pieces separately, and then combining the results. So they would not get the benefit of using "goroutines" rather than threads, a benefit which is important to the performance of many Go programs.

enneff 13y ago
Goroutines are not primarily about performance, they are for modelling concurrent processes in a natural way. This can have a performance in some cases, but I wouldn't classify goroutines the way you have.
- rubinelli 13y ago
  Excuse my ignorance, but could you use goroutines with different algorithms and pick the one that finishes first? Perhaps not in the case of MD5/SHA1, but for problems that have some algorithms that are very fast most of the time, but have a pathological worst case?
  - jgrahamc 13y ago
    Yes, you could do that. It would be very simple to give the same channel to two goroutines. Each goroutine would transmit the solution on the channel. You would just wait around to get the first item off the channel. Toy example: http://play.golang.org/p/imM9nOwer_ http://play.golang.org/p/imM9nOwer_
  - numbernein 13y ago
    Go has no way to abort a goroutine so if you tried multiple algorithms you would use total CPU time for all algorithms. Unlike actual threads Go gives no assurance that goroutines are preemptively scheduled, so doing so might take worst case time anyway. Even worse, there is no guarantee that new goroutines run next so doing so could introduce a scheduling delay. So basically it would be a terrible idea to do this in Go. With C/pthreads it might have some use in some really exceptional case. These are all reasons of course why goroutines are a bad idea. They should have just used threads, but apparently they wanted to support 32-bit architectures or some archaic OSes where threads have a high unit cost.
    - enneff 13y ago
      Gccgo did use threads for each goroutine for a while, and it was significantly slower than the gc "green thread" style implementation (used by both compilers today). Goroutines weigh in at about 4k each. OS threads are 64k minimum. That allows more than an order of magnitude more goroutines than threads, from a memory perspective. From an execution standpoint, goroutines managed by the Go runtime allow some nice scheduling optimisations, as the runtime is aware of the communication between goroutines. (some of these optimisations are in Go 1.1) Finally, there is no reason goroutines can't be preemptively scheduled. It is just an implementation detail, and work has already begun on this front.
      - teenth 13y ago
        Gccgo didn't have a garbage collector for a while, around the same time it was using threads. Was it even using a pool? Did it run goroutines for a short time on the current thread before moving to its own thread? Certainly not. Thread overhead in Linux is 8k, only slightly more than goroutine. It's 24k for windows. You guys don't even know basic facts that should have guided the design.
        enneff 13y ago
        Really? Can a Linux process spawn 1m threads? I didn't work on the design. If I made a mistake that's my fault. The people that did design Go and implement the runtime know what they're doing. You didn't respond to my other points, either.
        teenth 13y ago
        Yes a Linux process can spawn 1m threads, and testlimit64.exe spawned 250k threads both with 64k user stack and 1 MiB user stack... because that is just reserved address space if it isn't actually used. Only the kernel overhead matters to how many threads. I'm not sure what point you want addressed... scheduling optimization? It's also a deoptimization in other ways, such as predictable latency and fairness. I agree the designers knew what they were doing: designing a 'modern' language for 32-bit computers. The question is why?
jesstaa 13y ago
goroutines don't help with parallelization, they only help with concurrency.
- pcwalton 13y ago
  Huh? If you run with GOMAXPROCS=(some number greater than 1) goroutines will be multiplexed onto multiple OS threads.
  - jesstaa 13y ago
    Yep, and threads are what are helping with the parallelism. Goroutines don't make parallelism any faster or easier than threads do. But they make concurrency much simpler.

enneff 13y ago

Goroutines are not primarily about performance, they are for modelling concurrent processes in a natural way. This can have a performance in some cases, but I wouldn't classify goroutines the way you have.

rubinelli 13y ago
Excuse my ignorance, but could you use goroutines with different algorithms and pick the one that finishes first? Perhaps not in the case of MD5/SHA1, but for problems that have some algorithms that are very fast most of the time, but have a pathological worst case?
- jgrahamc 13y ago
  Yes, you could do that. It would be very simple to give the same channel to two goroutines. Each goroutine would transmit the solution on the channel. You would just wait around to get the first item off the channel. Toy example: http://play.golang.org/p/imM9nOwer_ http://play.golang.org/p/imM9nOwer_
- numbernein 13y ago
  Go has no way to abort a goroutine so if you tried multiple algorithms you would use total CPU time for all algorithms. Unlike actual threads Go gives no assurance that goroutines are preemptively scheduled, so doing so might take worst case time anyway. Even worse, there is no guarantee that new goroutines run next so doing so could introduce a scheduling delay. So basically it would be a terrible idea to do this in Go. With C/pthreads it might have some use in some really exceptional case. These are all reasons of course why goroutines are a bad idea. They should have just used threads, but apparently they wanted to support 32-bit architectures or some archaic OSes where threads have a high unit cost.
  - enneff 13y ago
    Gccgo did use threads for each goroutine for a while, and it was significantly slower than the gc "green thread" style implementation (used by both compilers today). Goroutines weigh in at about 4k each. OS threads are 64k minimum. That allows more than an order of magnitude more goroutines than threads, from a memory perspective. From an execution standpoint, goroutines managed by the Go runtime allow some nice scheduling optimisations, as the runtime is aware of the communication between goroutines. (some of these optimisations are in Go 1.1) Finally, there is no reason goroutines can't be preemptively scheduled. It is just an implementation detail, and work has already begun on this front.
    - teenth 13y ago
      Gccgo didn't have a garbage collector for a while, around the same time it was using threads. Was it even using a pool? Did it run goroutines for a short time on the current thread before moving to its own thread? Certainly not. Thread overhead in Linux is 8k, only slightly more than goroutine. It's 24k for windows. You guys don't even know basic facts that should have guided the design.
      - enneff 13y ago
        Really? Can a Linux process spawn 1m threads? I didn't work on the design. If I made a mistake that's my fault. The people that did design Go and implement the runtime know what they're doing. You didn't respond to my other points, either.
        teenth 13y ago
        Yes a Linux process can spawn 1m threads, and testlimit64.exe spawned 250k threads both with 64k user stack and 1 MiB user stack... because that is just reserved address space if it isn't actually used. Only the kernel overhead matters to how many threads. I'm not sure what point you want addressed... scheduling optimization? It's also a deoptimization in other ways, such as predictable latency and fairness. I agree the designers knew what they were doing: designing a 'modern' language for 32-bit computers. The question is why?

jesstaa 13y ago

goroutines don't help with parallelization, they only help with concurrency.

pcwalton 13y ago
Huh? If you run with GOMAXPROCS=(some number greater than 1) goroutines will be multiplexed onto multiple OS threads.
- jesstaa 13y ago
  Yep, and threads are what are helping with the parallelism. Goroutines don't make parallelism any faster or easier than threads do. But they make concurrency much simpler.