Skip to content
Snippets Groups Projects
  1. Dec 19, 2012
  2. Dec 17, 2012
  3. Dec 14, 2012
  4. Dec 13, 2012
    • Iustin Pop's avatar
      Log only partial response in Luxi when in debug mode · f74b88fa
      Iustin Pop authored
      
      Currently, we log the entire response (at debug level) in the Luxi
      replies. This is not a good idea; the logging library operates on
      strings, and as such it will use huge amounts of memory: without debug
      logging, a certain gnt-job list invocation uses 295MB (+RTS -s) and
      2m35s time, when in debug mode, it's 1525MB and 48m!
      
      So we make two changes:
      
      - first, we switch from "show (pp_value a)" to "encode a", which
        generates a non-formatted string rather than a indented one
      - second we log only the first 2000 characters; this should be enough
        to understand the first part of the response
      
      We could go for higher, or for logging in batches (that would be
      faster, as well).
      
      Signed-off-by: default avatarIustin Pop <iustin@google.com>
      Reviewed-by: default avatarHelga Velroyen <helgav@google.com>
      f74b88fa
  5. Dec 12, 2012
  6. Dec 11, 2012
  7. Dec 10, 2012
  8. Dec 07, 2012
  9. Dec 06, 2012
  10. Dec 05, 2012
  11. Dec 04, 2012
    • Guido Trotter's avatar
      Add "proper coloring" unittest check · c94f9990
      Guido Trotter authored
      
      We have to check that for each edge its vertices have different colors.
      
      This is very easy to do with a vertex-to-color map, but not so easy with
      a color-to-vertex one. Since all our coloring algorithms created a
      vertex-to-color map behind the scenes and then converted it, we flip
      them back to returning it directly, and do the conversion explicitly
      where we need it (which for now is everywhere except when testing this
      property).
      
      Signed-off-by: default avatarGuido Trotter <ultrotter@google.com>
      Reviewed-by: default avatarIustin Pop <iustin@google.com>
      c94f9990
    • Guido Trotter's avatar
      Fix Dsatur and add Dcolor · 8b50de5c
      Guido Trotter authored
      
      Our Dsatur implementation was incorrect: while the paper defined the
      degree of saturation of a vertex as the number of different colors it is
      adjacent to, we were using the number of colors, without considering
      uniqueness. This effectively implemented a different algorithm, which is
      very similar to the previous one, and while it performs slightly worse
      on average it still beats Dsatur on some cases.
      
      So we refactor the implementation to effectively support both algorithms
      without code duplication, and then we export both the old algorithms as
      "Dcolor" and the new one as "Dsatur". Since these are all fast
      algorithms in hroller we will still be able to pick the best result.
      
      Note that the new Dsatur implementation uses an IntSet to calculate the
      uniqueness. Results with nub + length on a list were significantly
      slower.
      
      Signed-off-by: default avatarGuido Trotter <ultrotter@google.com>
      Reviewed-by: default avatarIustin Pop <iustin@google.com>
      8b50de5c
    • Guido Trotter's avatar
      HTools/Node: add mkNodeGraph function · dae1f9cb
      Guido Trotter authored
      
      This function helps treating node node problems as graph problems.
      It can transform a list of nodes plus a list of instances into a graph
      which uses the nodes as vertices, and instances as edges connecting them
      (as long as they have both a primary and a secondary node)
      
      Signed-off-by: default avatarGuido Trotter <ultrotter@google.com>
      Reviewed-by: default avatarIustin Pop <iustin@google.com>
      dae1f9cb
    • Guido Trotter's avatar
      Ganeti/HTools/Graph Add isColorable · faef859e
      Guido Trotter authored
      
      Check whether coloring on a given graph makes sense. This is the case
      only if there are no loops and the graph is undirected.
      
      Signed-off-by: default avatarGuido Trotter <ultrotter@google.com>
      Reviewed-by: default avatarIustin Pop <iustin@google.com>
      faef859e
    • Guido Trotter's avatar
      Add Dsatur implementation · 742bd043
      Guido Trotter authored
      
      Implement the Dsatur algorithm for Graph coloring. This also abstracts
      the neighColors function into two subfunctions that this algorithm can
      reuse.
      
      Signed-off-by: default avatarGuido Trotter <ultrotter@google.com>
      Reviewed-by: default avatarIustin Pop <iustin@google.com>
      742bd043
Loading