13

Here's a small illustration of my question:

Assume a build job that consists of 4 independent tasks named A-D. D takes longer than A-C do in sum.

A build system that cannot incorporate the relative task times might schedule the tasks like this:

---------------------------------------
CPU1: A  |    C   |
---------------------------------------
CPU2: B    | D                        |
---------------------------------------

In contrast, if the scheduler is aware of the task time differences, it could come up with this much shorter schedule:

---------------------------------------
CPU1: A  |  B    |   C   |
---------------------------------------
CPU2: D                        |
---------------------------------------

My questions:

  1. Are there any build systems that incorporate relative expected task times into the schedule?
  2. What academic research into build systems of this kind exists?
  3. Where do these build systems (if they exist) take the time information from? Heuristics, timings collected during previous builds?
  4. If such build systems do not exist, why? Is there a gotcha that would make them less worthwile than they appear at first glance?
  • 3
    Most questions for third party resources or tools are closed quickly as "off-topic", but I guess this one could be an edge case which seem to fit well to the scope of this site. – Doc Brown Jan 29 '17 at 18:11
  • 1
    I think this is based on the wrong assumption that "building" a task is non-parallel. – dagnelies Feb 4 '17 at 20:18
  • In most cases, building a task is indeed non-parallel, but yes, e.g. unit tests in multi-threaded applications can indeed be parallel. Actually, in a project where I work we always have to invoke "make" with "-j1" for the unit test run, because otherwise performance related multicore unit tests fail. – juhist Feb 6 '17 at 13:58
  • @juhist In case you're interested in switching to a more expressive build system, shake has a concept of resources where you can for example define how many CPU cores should be reserved for your unit tests. – sjakobi Feb 6 '17 at 15:18
3
+50

Microsoft Visual Studio Team System (formerly TFS) does consider build action times and parallel builds; it takes the data from previous build history; and while I don't believe you can get the behavior you want out of the box, you may be able to customize it.

An example of some custom tasks to work on optimizing performance

https://veegens.wordpress.com/2013/03/26/tfs-2010-build-performance-report/

  • If I understand your answer and your link correctly, build action times are reported (which is rather common feature) but it's not clear whether or how these timings could be used for improving the build schedule. This doesn't really seem to answer my original question(s), so I won't award the bounty to your answer. – sjakobi Feb 1 '17 at 10:10
  • No problem, what you may have missed is that you can customize build actions and the build process, through programming. The sample was reporting, but as stated, history is taken for automatic optimizations. Also, note that you can configure parallel builds. But then to make sure they are parallelized following your algorithm, you may need to customize with code. Some additional reference: dotnetcurry.com/visualstudio/1177/… – Bruno Guardia Feb 1 '17 at 15:51
  • 2
    @BrunoGuardia: can you explan where in that article of your link is a customization option mentioned which could help to utilize the expected task times of the build actions? – Doc Brown Feb 3 '17 at 16:12
0

This is based on the wrong assumption that "building" a task is non-parallel.

Many compilers work multi-threaded, so a single task A will use all CPUs. Therefore, the order doesn't matter. For I/O bound tasks, especially involving networking, better start them all parallely from the start too: most time will be spent waiting for an answer.

In other words, ordering does not matter since the individual tasks are typically parallelized (like compiling for instance)


Edit:

Actually, this conception of "Task A on CPU 1" is flawed too. Even for single threaded tasks, the OS scheduling the processes/threads may hop it from CPU to CPU on each context switch. I guess most build systems will just run all tasks in parallel and let the OS do the scheduling. Longer tasks will take longer and that's about it.

Assuming you have a long running single threaded task that's not I/O bound, it would be way easier for the build system to assign it a priority/importance rather to attempt to delay smaller tasks to reduce context switches from the OS.

Even if you have such strange tasks, which is quite rare in practice, and have a fancy scheduling build system which works on heuristics based on previous runs (the only way to know), the benefits you get from it may be rather small ...however you get a bunch of added complexity to maintain.

  • "Within-task" parallelism is an interesting aspect and certainly offers additional potential for optimization, but I don't think that assuming that any given task will scale efficiently to an arbitrary number of CPUs is any better than assuming that each task must run on a single core. – sjakobi Feb 5 '17 at 2:09
  • @sjakobi: well, in practice it's quite important that compilers are efficient. Can you imagine that you wait a long time for your compiling because only 1 of your 16 cores is used? That's a no-go. With all the theory you seem to overlook the reality. Scheduling is a very interesting and very meaningful topic. It's just IMHO relatively useless in the context of build systems. Again, most compilers nowadays are multithreaded anyway ...and if they are not, effort should much rather be put into this rather the scheduling build system. – dagnelies Feb 5 '17 at 10:51
  • 2
    All free software compilers (GCC & Clang...) for C++ or C or Fortran or Ada are mono-threaded. The build system (make -j) can launch several compilation processes in parallel. – Basile Starynkevitch Feb 5 '17 at 13:22
  • @BasileStarynkevitch: ...indeed. Basically, everybody sane uses -j <nb-cores> but sadly the default is still "1" ...I'm still surprised it never changed. – dagnelies Feb 5 '17 at 14:28
  • @dagnelies: There is a huge number of Makefiles that miss some critical dependencies and thus don't work (or may not work) with -jN where N>1. – juhist Feb 6 '17 at 14:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.