1. 24 Jul, 2020 3 commits
  2. 23 Jul, 2020 6 commits
  3. 22 Jul, 2020 25 commits
    • 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
    • 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
      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
    • Benjamin Otte's avatar
      sortlistmodel: Add an incremental property · 283c3b70
      Benjamin Otte authored
      Also refactor a large part of the sortmodel to make this convenient.
      
      A large amount of time has been spent on getting items-changed regions
      minimized.
      283c3b70
    • Benjamin Otte's avatar
      sortlistmodel: Make the sort callback useful · 080e6250
      Benjamin Otte authored
      1. Run step() for a while to avoid very short steps
         This way, we batch items-changed() emissions.
      
      2. Track the change region accurately
         This way, we can avoid invalidating the whole list if our step just
         touched a small part of a huge list.
         As this is a merge sort, this is a common occurence when we're buys
         merging chunks: The rest of the model outside those chunks isn't
         changed.
      
      Note that the tracking is accurate: It determines the minimum change
      region in the model.
      
      This will be important, because the testsuite is going to test this.
      080e6250
    • Benjamin Otte's avatar
      26696a74
    • Benjamin Otte's avatar
      timsort: Add gtk_tim_sort_set_max_merge_size() · a209e54b
      Benjamin Otte authored
      Makes the SOrtListModel responsive when incrementally sorting.
      
      By making it configurable we can avoid losting performance in the
      non-incremental case.
      a209e54b
    • Benjamin Otte's avatar
      timsort: Make sure merges don't take too long · 8921dada
      Benjamin Otte authored
      Limit the size of the merged areas and thereby chunk larger merges into
      smaller ones.
      8921dada
    • Benjamin Otte's avatar
      sortlistmodel: Make sorting incremental · 47232acb
      Benjamin Otte authored
      This is just an experiment so far to see how long it takes to sort.
      47232acb
    • Benjamin Otte's avatar
      timsort: Add gtk_tim_sort_set_runs() · cbad8ec2
      Benjamin Otte authored
      ... and use it in the SortListModel
      
      Setting runs allows declaring already sorted regions so the sort does
      not attempt to sort them again.
      
      This massively speeds up partial inserts where we can reuse the sorted
      model as a run and only resort the newly inserted parts.
      
      Benchmarks:
      
          appending half the model
                          qsort  timsort
          128,000 items    94ms     69ms
          256,000 items   202ms    143ms
          512,000 items   488ms    328ms
      
          appending 1 item
                          qsort  timsort
            8,000 items   1.5ms    0.0ms
           16,000 items   3.1ms    0.0ms
                    ...
          512,000 items     ---    1.8ms
      cbad8ec2
    • Benjamin Otte's avatar
      sortlistmodel: Use timsort · 800170b4
      Benjamin Otte authored
      Simply replace the old qsort() call with a timsort() call.
      
      This is ultimately relevant because timsort is a LOT faster in merging
      to already sorted lists (think items-chaged adding some items) or
      reversing an existing list (think columnview sort order changes).
      
      Benchmarks:
      
          initially sorting the model
                          qsort  timsort
          128,000 items   124ms    111ms
          256,000 items   264ms    250ms
      800170b4
    • Benjamin Otte's avatar
      Add a timsort() implementation · 97c5cb35
      Benjamin Otte authored
      97c5cb35
    • Benjamin Otte's avatar
      sortlistmodel: Track item positions · 081afc04
      Benjamin Otte authored
      The model now tracks the original positions on top of just the items so that
      it can remove items in an items-changed emission.
      
      It now takes twice as much memory but removes items much faster.
      
      Benchmarks:
      
      Removing 50% of a model:
                         before    after
         250,000 items    135ms     10ms
         500,000 items    300ms     25ms
      
      Removing 1 item:
           4,000 items    2.2ms      0ms
           8,000 items    4.6ms      0ms
         500,000 items      ---   0.01ms
      081afc04
    • Benjamin Otte's avatar
      sortlistmodel: Replace with an array-based model · e807fc3b
      Benjamin Otte authored
      This is the dumbest possible sortmodel using an array:
      Just grab all the items, put them in the array, qsort() the array.
      
      Some benchmarks (setting a new model):
      
        125,000 items - old: 549ms
                        new: 115ms
        250,000 items - new: 250ms
      
      This performance can not be kept for simple additions and removals
      though.
      e807fc3b
  4. 21 Jul, 2020 1 commit
  5. 20 Jul, 2020 5 commits