1. 24 Jul, 2020 6 commits
  2. 23 Jul, 2020 11 commits
  3. 22 Jul, 2020 23 commits
    • Matthias Clasen's avatar
      NEWS: Updates · fb628879
      Matthias Clasen authored
      fb628879
    • Matthias Clasen's avatar
      migration guide: Add some tables · 2160f52c
      Matthias Clasen authored
      Add a table mapping event signals to their event controller
      replacements, and a table mapping former GtkContainer
      subclasses to their gtk_container_add replacement.
      2160f52c
    • Benjamin Otte's avatar
      Merge branch 'wip/otte/for-master' into 'master' · 8825e621
      Benjamin Otte authored
      timsort: Actually 0-terminate the array in get_runs()
      
      See merge request !2274
      8825e621
    • Benjamin Otte's avatar
      timsort: Actually 0-terminate the array in get_runs() · e22abd73
      Benjamin Otte authored
      This could cause SEGVs when changing the sort during an ongoing sort
      operation.
      e22abd73
    • Yuri Chornoivan's avatar
      Update Ukrainian translation · f77d4d7f
      Yuri Chornoivan authored and Administrator's avatar Administrator committed
      f77d4d7f
    • Yuri Chornoivan's avatar
      Update Ukrainian translation · 8243133c
      Yuri Chornoivan authored and Administrator's avatar Administrator committed
      8243133c
    • Matthias Clasen's avatar
      Merge branch 'wip/otte/sortlistmodel2' into 'master' · 63a4345d
      Matthias Clasen authored
      Massively refactor and improve sortlistmodel
      
      See merge request !2273
      63a4345d
    • Piotr Drąg's avatar
      Update POTFILES.in · 56685a48
      Piotr Drąg authored
      56685a48
    • Benjamin Otte's avatar
    • Benjamin Otte's avatar
      sortlistmodel: Add progress estimation · 2b19e2fc
      Benjamin Otte authored
      2b19e2fc
    • Benjamin Otte's avatar
      timsort: Add progress estimation · 703f8b81
      Benjamin Otte authored
      703f8b81
    • Benjamin Otte's avatar
      sortlistmodel: Make key generation part of the step function · 5b189688
      Benjamin Otte authored
      SSave the missing keys as a bitset and iterate over that bitset in the
      step function.
      
      Solves the problem with a large UI block at the beginning of a sort
      operation when all the keys were generated, in particular when key
      generation was slow.
      
      Benchmarks for maximum time taken by a single main loop callback:
      
           initial sort with complex GFileInfo keys
                             old      new
            32,000 items   137ms      3ms
           128,000 items   520ms     31ms
      
           initial sort with string keys
                             old      new
            32,000 items   187ms      1ms
           128,000 items   804ms      3ms
      5b189688
    • Benjamin Otte's avatar
      e8c4e120
    • Benjamin Otte's avatar
      sortlistmodel: Properly compute runs · bf5c5403
      Benjamin Otte authored
      When updating a (partially) sorted model, take the known runs for the
      existing sort and apply them to the new sort. That way, we don't have to
      check the whole model again.
      
      Benchmarks:
      
            appending half the items to a model of strings
                              old      new
            512,000 items   437ms    389ms
          1,024,000 items  1006ms    914ms
      
            appending 10% of the items to a model of strings
                              old      new
            512,000 items   206ms    132ms
          1,024,000 items   438ms    301ms
      
            appending 1 item to a model of strings
                              old      new
             64,000 items   1.8ms   0.00ms
            512,000 items     ---   0.01ms
      bf5c5403
    • Benjamin Otte's avatar
      sortlistmodel: Make sort stable again · c03383d3
      Benjamin Otte authored
      Previously, the sort was not stable when items were added/removed while
      sorting or the sort algorithm was changed.
      
      Now the sort looks at the item position (via the key's location in the
      keys array) to make sure each comparison stays stable with respect to
      this position.
      c03383d3
    • Benjamin Otte's avatar
      multisorter: Implement GtkSortKeys · eaaa2870
      Benjamin Otte authored
      eaaa2870
    • Benjamin Otte's avatar
      treelistrowsorter: Implement GtkSortKeys · 554defaf
      Benjamin Otte authored
      554defaf
    • Benjamin Otte's avatar
      numericsorter: Implement GtkSortKeys · 659fe52b
      Benjamin Otte authored
      659fe52b
    • Benjamin Otte's avatar
      stringsorter: Implement GtkSortKeys · 0970077a
      Benjamin Otte authored
      0970077a
    • Benjamin Otte's avatar
      sortkeys: Add an equal sort keys · 814c88fb
      Benjamin Otte authored
      Compares every element as equal.
      This is useful when sorters are in an invalid configuration.
      814c88fb
    • Benjamin Otte's avatar
      sortlistmodel: Use GtkSortKeys · 3b24c8a0
      Benjamin Otte authored
      This massively speeds up sorting with expensive sort functions that it's
      the most worthwhile optimization of this whole branch.
      It's slower for simple sort functions though.
      
      It's also quite a lot slower when the model doesn't support sort keys
      (like GtkCustomSorter), but all the other sorters do support keys.
      
      Of course, this depends on the number of items in the model - the number
      of comparisons scales O(N * log N) while the overhead for key handling
      scales O(N).
      So as the log N part grows, generating keys gets more and more
      beneficial.
      
      Benchmarks:
      
             initial sort of a GFileInfo model with display-name keys
                             items     keys
               8,000 items   715ms     50ms
              64,000 items     ---    554ms
      
             initial sort of a GFileInfo model with complex keys
                             items     keys
              64,000 items   340ms    295ms
             128,000 items   641ms    605ms
      
             removing half a GFileInfo model with display-name keys
             (no comparisons, just key freeing overhead of a complex sorter)
                             items     keys
             512,000 items    14ms     21ms
           2,048,000 items    40ms     62ms
      
             removing half a GFileInfo model with complex keys
             (no comparisons, just key freeing overhead of a complex sorter)
                             items     keys
             512,000 items    90ms    237ms
           2,048,000 items   247ms    601ms
      3b24c8a0
    • Benjamin Otte's avatar
      sorter: Introduce GtkSortKeys · e34c7e67
      Benjamin Otte authored
      GtkSortKeys is an immutable struct that can be used to manage "sort
      keys" for items.
      
      Sort keys are memory that is created specifically for sorting. Because
      sorting involves lots of comparisons, it's a good idea to prepare the
      data relevant for sorting in advance and sort on that data.
      
      In measurements with a PropertyExpression on a string sorter, it's about
      ??? faster
      e34c7e67
    • Benjamin Otte's avatar
      sortlistmodel: Split the SortItem into 2 arrays · 8c608e9c
      Benjamin Otte authored
      Instead of one item keeping the item + its position and sorting that
      list, keep the items in 1 array and put the positions into a 2nd array.
      
      This is generally slower while sorting, but allows multiple improvements:
      
      1. We can replace items with keys
         This allows avoiding multiple slow lookups when using complex
         comparisons
      
      2. We can keep multiple position arrays
         This allows doing a sorting in the background without actually
         emitting items-changed() until the array is completely sorted.
      
      3. The main list tracks the items in the original model
         So only a single memmove() is necessary there, while the old version
         had to upgrade the position in every item.
      Benchmarks:
      
              sorting a model of simple strings
                                old      new
              256,000 items   256ms    268ms
              512,000 items   569ms    638ms
      
              sorting a model of file trees, directories first, by size
                                old      new
               64,000 items   350ms    364ms
              128,000 items   667ms    691ms
      
              removing half the model
                                old      new
              512,000 items    24ms     15ms
            1,024,000 items    49ms     25ms
      8c608e9c