Re: [whatwg] [Web workers] An attribute describing the best number of worker to invoke in a delegation use case
Ian Hickson a écrit : On Wed, 11 Nov 2009, David Bruant wrote: This is a new proposal taking into account the feedback I recieved to the [WebWorkers] About the delegation example message. In the delegation example of the WebWorker spec, we can see this line : var num_workers = 10; My concern is about the arbitrarity of the 10. I agree that it's suboptimal. However, I think realistically a good implementation of parallel work would need some sort of dynamic performance tuning, continuously slowly ramping up the number of workers while it increases throughput, and when throughput decreases, switching to reducing the number of workers until throughput increases again. That would probably be too complicated to show in an example in the spec. = As far as I know, if the running time is a decreasing function of the number of workers (which seems to be a non-such-trivial assumption), the best algorithm (on average, of course !) is to double the number of workers until finding a barrier in the running time (find n such as the max is between [2^n, 2^(n+1)[ ). Then, use a dichotomy algorithm in this interval. However, running this algorithm each time a UA comes in your website can become to be costly. I think that the spec should say something about finding the correct number of thread for your problem and encourage authors to store their value with the local storage and add a date to re-run the algorithm if the value is old (more than two months ?) My point is that this number may be available very easily. For example, in my dual-core, Linux, Firefox 3.5, the number is 2. Why spare an information that can be useful and reliable (more than measurement at least !) ? It's actually probably quite rarely 2. It depends on all kinds of factors, like the kind of algorithm, what other programs are running, etc. I still haven't added this feature, as I do not believe the arguments presented form a convincing case. However, if you are still interested in persuing this feature, I encourage you to convince a browser vendor to implement it, as discussed here: http://wiki.whatwg.org/wiki/FAQ#Is_there_a_process_for_adding_new_features_to_a_specification.3F Cheers, I understand now that my proposition was not very realistic. However, I think that something should be described in the spec to avoid arbitrary choices of number of workers. I'm convinced that with canvas and workers, we will see very soon fancy web video games with AI. Authors of those games will want to use as many computation power as possible for their AI, so the best number of workers will be a value that they are interested in. So, either an hint can be provided by the spec through the Navigator object, either the spec could provide the above described method (improve my description or ask me to improve it if you want) to find the best number (according to a particular problem). Thanks, David
Re: [whatwg] [Web workers] An attribute describing the best number of worker to invoke in a delegation use case
On Wed, 11 Nov 2009, David Bruant wrote: This is a new proposal taking into account the feedback I recieved to the [WebWorkers] About the delegation example message. In the delegation example of the WebWorker spec, we can see this line : var num_workers = 10; My concern is about the arbitrarity of the 10. I agree that it's suboptimal. However, I think realistically a good implementation of parallel work would need some sort of dynamic performance tuning, continuously slowly ramping up the number of workers while it increases throughput, and when throughput decreases, switching to reducing the number of workers until throughput increases again. That would probably be too complicated to show in an example in the spec. My proposal is to add an attribute to the navigator object to write this : var num_workers = navigator.optimalWorkerNumber; var items_per_worker = 1000/num_workers; (uneven dividing can easily be solved) (the name optimalWorkerNumber is not good, but I will use it in the rest of this e-mail) optimalWorkerNumber is a function of time and of the algorithm that the worker implements. I don't think it would solve the problem. This attribute have the following properties : - It's only dependant on the hardware, the operating system and the WebWorker implementation (thus, it is not dynamically computed by the user agent at each call and two calls in the same hardware//OS//WebWorker implementation have the same result). - In the same running conditions (same memory available, same number of process running concurrently...) running the same algorithm (an easy delegation algorithm) has a significantly better performance with (navigator.optimalWorkerNumber) workers than (navigator.optimalWorkerNumber - 1) workers - In the same running conditions, running the same algorithm has no significantly better performance with (navigator.optimalWorkerNumber +1) workers than (navigator.optimalWorkerNumber) workers I do not think it is possible to satisfy all of the above conditions at the same time. On Thu, 12 Nov 2009, David Bruant wrote, in response to Boris saying much the same as what I wrote above: = You're perfectly right. I reformulate the definition of running conditions (appearing in condition 2 and 3) as : same memory available, same number of process running concurrently, no other worker running working on the same document. On Thu, 12 Nov 2009, Boris Zbarsky wrote: That doesn't help that much, unfortunately. Most simply, consider a quad-core chip and workers that are completely cpu-bound. If there are no other processes running, the optimal number of workers is 4. If there is one other process which is also completely cpu-bound running, the optimal number of workers is 3 (in the sense that 4 may well not satisfy your condition 3). This is really the same issue as having one worker running, but it's some process not under the browser's control. If, on the other hand, the workers are I/O bound (esp. network I/O latency bound), then the optimal number of workers can well be larger than the number of cores... On Thu, 12 Nov 2009, David Bruant wrote: = If you are comparing no other processes running and one other process which is also completely cpu-bound running, you are not in what I've called same running conditions. (because the number of concurrent processes is different). The point is that the constant can't be constant if it has to return a different number based on conditions outside the UA's control. I reformulate this way the conditions 2 and 3: - In blank conditions (no other processes/thread running on the CPU, enough memory to allocate the workers), running the same algorithm (an easy delegation algorithm) has significantly better performances with (navigator.optimalWorkerNumber) dedicated workers than with (navigator.optimalWorkerNumber -1) dedicated workers - In blank conditions, running the same algorithm has no significantly better performances with (navigator.optimalWorkerNumber+1) dedicated workers than with (navigator.optimalWorkerNumber) dedicated workers This isn't especially useful, since blank conditions are never met by a running script (for one, the script is running). Just to remind, the purpose of this attribute is to decide, at the beginning of a delegation algorithm what is the optimal number of workers to divide the work in a way that is optimal regarding the hardware, the OS and the worker implementation. No matter the running conditions, 2 calls return the same value for the same hardware//OS//Worker implementation. The idea behind this property is that even if you start running the algorithm with a lot of concurrent processes, you create a number of workers that cannot be ran concurrently at the beginning, but you may use optimally the ressources later (if the other processes/threads stop running, what you cannot control, but can still hope that it happens
Re: [whatwg] [Web workers] An attribute describing the best number of worker to invoke in a delegation use case
Boris Zbarsky a écrit : On 11/11/09 10:19 PM, David Bruant wrote: This attribute have the following properties : - It's only dependant on the hardware, the operating system and the WebWorker implementation (thus, it is not dynamically computed by the user agent at each call and two calls in the same hardware//OS//WebWorker implementation have the same result). - In the same running conditions (same memory available, same number of process running concurrently...) running the same algorithm (an easy delegation algorithm) has a significantly better performance with (navigator.optimalWorkerNumber) workers than (navigator.optimalWorkerNumber - 1) workers - In the same running conditions, running the same algorithm has no significantly better performance with (navigator.optimalWorkerNumber +1) workers than (navigator.optimalWorkerNumber) workers I believe that these conditions are mutually contradictory. Indeed, condition 1 requires that optimalWorkerNumber be a constant independent of what the browser itself and other applications are doing. = That is what I meant (and still mean) Condition 2 requires that running with navigator.optimalWorkerNumber has better performance than running with (navigator.optimalWorkerNumber - 1) workers. In particular, it requires that this be the case even if there is already one worker doing something (due to condition 1). This implies that performance with (navigator.optimalWorkerNumber+1) workers be better than that with navigator.optimalWorkerNumber workers, which directly violates condition 3. = You're perfectly right. I reformulate the definition of running conditions (appearing in condition 2 and 3) as : same memory available, same number of process running concurrently, no other worker running working on the same document. David -Boris
Re: [whatwg] [Web workers] An attribute describing the best number of worker to invoke in a delegation use case
On 11/12/09 12:49 PM, David Bruant wrote: = You're perfectly right. I reformulate the definition of running conditions (appearing in condition 2 and 3) as : same memory available, same number of process running concurrently, no other worker running working on the same document. That doesn't help that much, unfortunately. Most simply, consider a quad-core chip and workers that are completely cpu-bound. If there are no other processes running, the optimal number of workers is 4. If there is one other process which is also completely cpu-bound running, the optimal number of workers is 3 (in the sense that 4 may well not satisfy your condition 3). This is really the same issue as having one worker running, but it's some process not under the browser's control. If, on the other hand, the workers are I/O bound (esp. network I/O latency bound), then the optimal number of workers can well be larger than the number of cores... -Boris
Re: [whatwg] [Web workers] An attribute describing the best number of worker to invoke in a delegation use case
Boris Zbarsky a écrit : On 11/12/09 12:49 PM, David Bruant wrote: = You're perfectly right. I reformulate the definition of running conditions (appearing in condition 2 and 3) as : same memory available, same number of process running concurrently, no other worker running working on the same document. That doesn't help that much, unfortunately. Most simply, consider a quad-core chip and workers that are completely cpu-bound. If there are no other processes running, the optimal number of workers is 4. If there is one other process which is also completely cpu-bound running, the optimal number of workers is 3 (in the sense that 4 may well not satisfy your condition 3). This is really the same issue as having one worker running, but it's some process not under the browser's control. = If you are comparing no other processes running and one other process which is also completely cpu-bound running, you are not in what I've called same running conditions. (because the number of concurrent processes is different). The condition 2 and 3 may be not well-expressed, however, the condition 1 is very important and particularly the fact that this number is independant of the running conditions (which are, IMHO, totally out of the scope of a high-level spec such as the web-workers one) and shouldn't be determined dynamically. I reformulate this way the conditions 2 and 3: - In blank conditions (no other processes/thread running on the CPU, enough memory to allocate the workers), running the same algorithm (an easy delegation algorithm) has significantly better performances with (navigator.optimalWorkerNumber) dedicated workers than with (navigator.optimalWorkerNumber -1) dedicated workers - In blank conditions, running the same algorithm has no significantly better performances with (navigator.optimalWorkerNumber+1) dedicated workers than with (navigator.optimalWorkerNumber) dedicated workers Just to remind, the purpose of this attribute is to decide, at the beginning of a delegation algorithm what is the optimal number of workers to divide the work in a way that is optimal regarding the hardware, the OS and the worker implementation. No matter the running conditions, 2 calls return the same value for the same hardware//OS//Worker implementation. The idea behind this property is that even if you start running the algorithm with a lot of concurrent processes, you create a number of workers that cannot be ran concurrently at the beginning, but you may use optimally the ressources later (if the other processes/threads stop running, what you cannot control, but can still hope that it happens during the algorithm lifetime. According to the spec, workers are expected to be long-lived). Thanks for your feedback David If, on the other hand, the workers are I/O bound (esp. network I/O latency bound), then the optimal number of workers can well be larger than the number of cores... -Boris
Re: [whatwg] [Web workers] An attribute describing the best number of worker to invoke in a delegation use case
On 11/12/09 3:40 PM, David Bruant wrote: = If you are comparing no other processes running and one other process which is also completely cpu-bound running, you are not in what I've called same running conditions. (because the number of concurrent processes is different). Yes, but your condition 1 is that the value returned is independent of running conditions The condition 2 and 3 may be not well-expressed, however, the condition 1 is very important and particularly the fact that this number is independant of the running conditions (which are, IMHO, totally out of the scope of a high-level spec such as the web-workers one) and shouldn't be determined dynamically. OK. I reformulate this way the conditions 2 and 3: - In blank conditions (no other processes/thread running on the CPU, enough memory to allocate the workers), running the same algorithm (an easy delegation algorithm) has significantly better performances with (navigator.optimalWorkerNumber) dedicated workers than with (navigator.optimalWorkerNumber -1) dedicated workers - In blank conditions, running the same algorithm has no significantly better performances with (navigator.optimalWorkerNumber+1) dedicated workers than with (navigator.optimalWorkerNumber) dedicated workers OK, but I'm not sure this is a useful number, then, since these blank conditions never happen in practice. Just to remind, the purpose of this attribute is to decide, at the beginning of a delegation algorithm what is the optimal number of workers to divide the work in a way that is optimal regarding the hardware, the OS and the worker implementation. I'm glad you put optimal in quotes ;) Is there a reason that apps that really care about this shouldn't just measure to see what number works best for them? The idea behind this property is that even if you start running the algorithm with a lot of concurrent processes, you create a number of workers that cannot be ran concurrently at the beginning, but you may use optimally the ressources later But in the meantime you will be using them very suboptimally, no? (if the other processes/threads stop running, what you cannot control, but can still hope that it happens during the algorithm lifetime. According to the spec, workers are expected to be long-lived). Most of my apps are long-lived... -Boris
Re: [whatwg] [Web workers] An attribute describing the best number of worker to invoke in a delegation use case
Boris Zbarsky a écrit : On 11/12/09 3:40 PM, David Bruant wrote: I reformulate this way the conditions 2 and 3: - In blank conditions (no other processes/thread running on the CPU, enough memory to allocate the workers), running the same algorithm (an easy delegation algorithm) has significantly better performances with (navigator.optimalWorkerNumber) dedicated workers than with (navigator.optimalWorkerNumber -1) dedicated workers - In blank conditions, running the same algorithm has no significantly better performances with (navigator.optimalWorkerNumber+1) dedicated workers than with (navigator.optimalWorkerNumber) dedicated workers OK, but I'm not sure this is a useful number, then, since these blank conditions never happen in practice. = I think it happens very often. While I'm writing this e-mail, no process is running. About fifty processes are runnable, but not running. They are passively waiting. My CPU is barely used. Just to remind, the purpose of this attribute is to decide, at the beginning of a delegation algorithm what is the optimal number of workers to divide the work in a way that is optimal regarding the hardware, the OS and the worker implementation. I'm glad you put optimal in quotes ;) = I'm fully aware that for a such high-level specification, talking about optimality (and even performance !) is very relative. Is there a reason that apps that really care about this shouldn't just measure to see what number works best for them? = I agree on the fact that this is the key question to decide if my proposal must be taken into account or not. My point is that this number may be available very easily. For example, in my dual-core, Linux, Firefox 3.5, the number is 2. Why spare an information that can be useful and reliable (more than measurement at least !) ? I also agree on the fact that this attribute is not the most important attribute in the world, but as the colorDepth attribute of the screen object (http://www.w3.org/TR/cssom-view/#dom-screen-colordepth), it will be useful to some people in some usecase. The idea behind this property is that even if you start running the algorithm with a lot of concurrent processes, you create a number of workers that cannot be ran concurrently at the beginning, but you may use optimally the ressources later But in the meantime you will be using them very suboptimally, no? = Yes and no. No one can know if they will be optimally used or not. What you are garanteed (quotes again) is that in blank conditions, they will be optimally used (which is more or less the definition of this number). (if the other processes/threads stop running, what you cannot control, but can still hope that it happens during the algorithm lifetime. According to the spec, workers are expected to be long-lived). Most of my apps are long-lived... -Boris
Re: [whatwg] [Web workers] An attribute describing the best number of worker to invoke in a delegation use case
On 11/12/09 7:24 PM, David Bruant wrote: = I think it happens very often. While I'm writing this e-mail, no process is running. About fifty processes are runnable, but not running. They are passively waiting. My CPU is barely used. Interesting. I have several browser processes using timeslices right now (the incessant XHR google apps tend to do, I think), plus at least two other things running that are fully using up one core and most of another, as I write this mail. I don't see how a browser could return a single number that would work or both of us. My point is that this number may be available very easily. For example, in my dual-core, Linux, Firefox 3.5, the number is 2. OK, what about in Firefox 3.6? If your worker plans to not allocate many strings and the like, it's 2. Otherwise, it's 1 (because a good bit of gc finalization has been moved to a separate thread). Why spare an information that can be useful and reliable (more than measurement at least !) ? Because the information is _not_ reliable. The optimal number of concurrent threads of execution given a given fixed set of computation resources is heavily dependent on the behavior of the threads of execution and what else is using the computation resources... Put another way, as a UA implementor I don't know what I'd make this attribute return without it being a bald-faced lie in pretty simple cases. = Yes and no. No one can know if they will be optimally used or not. What you are garanteed (quotes again) is that in blank conditions, they will be optimally used (which is more or less the definition of this number). See above; even in blank conditions this may well depend on the exact workload of your workers. -Boris
[whatwg] [Web workers] An attribute describing the best number of worker to invoke in a delegation use case
Hi, This is a new proposal taking into account the feedback I recieved to the [WebWorkers] About the delegation example message. In the delegation example of the WebWorker spec, we can see this line : var num_workers = 10; My concern is about the arbitrarity of the 10. Regarding the hardware, the operating system and the WebWorker implementation, on one hand, this 10 may not result in a better performance than if num_worker was equal to 1. On the other hand, the user agent configuration may have better performances with a greater number of workers (16 ? 100 ?). My proposal is to add an attribute to the navigator object to write this : var num_workers = navigator.optimalWorkerNumber; var items_per_worker = 1000/num_workers; (uneven dividing can easily be solved) (the name optimalWorkerNumber is not good, but I will use it in the rest of this e-mail) This attribute have the following properties : - It's only dependant on the hardware, the operating system and the WebWorker implementation (thus, it is not dynamically computed by the user agent at each call and two calls in the same hardware//OS//WebWorker implementation have the same result). - In the same running conditions (same memory available, same number of process running concurrently...) running the same algorithm (an easy delegation algorithm) has a significantly better performance with (navigator.optimalWorkerNumber) workers than (navigator.optimalWorkerNumber - 1) workers - In the same running conditions, running the same algorithm has no significantly better performance with (navigator.optimalWorkerNumber +1) workers than (navigator.optimalWorkerNumber) workers Thanks for your feedback (previous and coming) David
Re: [whatwg] [Web workers] An attribute describing the best number of worker to invoke in a delegation use case
On 11/11/09 10:19 PM, David Bruant wrote: This attribute have the following properties : - It's only dependant on the hardware, the operating system and the WebWorker implementation (thus, it is not dynamically computed by the user agent at each call and two calls in the same hardware//OS//WebWorker implementation have the same result). - In the same running conditions (same memory available, same number of process running concurrently...) running the same algorithm (an easy delegation algorithm) has a significantly better performance with (navigator.optimalWorkerNumber) workers than (navigator.optimalWorkerNumber - 1) workers - In the same running conditions, running the same algorithm has no significantly better performance with (navigator.optimalWorkerNumber +1) workers than (navigator.optimalWorkerNumber) workers I believe that these conditions are mutually contradictory. Indeed, condition 1 requires that optimalWorkerNumber be a constant independent of what the browser itself and other applications are doing. Condition 2 requires that running with navigator.optimalWorkerNumber has better performance than running with (navigator.optimalWorkerNumber - 1) workers. In particular, it requires that this be the case even if there is already one worker doing something (due to condition 1). This implies that performance with (navigator.optimalWorkerNumber+1) workers be better than that with navigator.optimalWorkerNumber workers, which directly violates condition 3. -Boris
