Optimize vectorized sorting - reduce code size, improve speed for large heaps (#40613)
authorPeter Sollich <petersol@microsoft.com>
Thu, 13 Aug 2020 10:09:49 +0000 (12:09 +0200)
committerGitHub <noreply@github.com>
Thu, 13 Aug 2020 10:09:49 +0000 (12:09 +0200)
commit2fd135f1b14bfc7ee0d715c37809f1fbdc41739f
tree4faef5023c49dc99591334e827e92cbc7d18e470
parent3c29684ba59cb7999aab0223648e66eb3a3e079a
Optimize vectorized sorting - reduce code size, improve speed for large heaps (#40613)

* Improved vectorized sort - smaller bitonic sorters, dynamic packing/unpacking.

There are two optimizations in this PR:

- reduction of code size in the bitonic sorters: by limiting the amount of inlining in this code, we can reduce overall code size in coreclr.dll by about 180 kB.

- dynamic packing: during sorting, we can switch to 32-bit sorting as soon as the address range in a partition is less 32 GB. This will only have an impact on large heaps or machines with many processors, because we already have a similar, but static optimization where we use 32-bit sorting if the overall address range in the ephemeral region is less than 32 GB. So this additional optimization will give improvements if the overall address range is greater than 32 GB initially, but becomes less during the sort. In this case, we get about a 1.6x improvement in sorting speed.
30 files changed:
src/coreclr/src/gc/CMakeLists.txt
src/coreclr/src/gc/gc.cpp
src/coreclr/src/gc/sample/CMakeLists.txt
src/coreclr/src/gc/vxsort/alignment.h
src/coreclr/src/gc/vxsort/defs.h
src/coreclr/src/gc/vxsort/do_vxsort.h
src/coreclr/src/gc/vxsort/do_vxsort_avx2.cpp
src/coreclr/src/gc/vxsort/do_vxsort_avx512.cpp
src/coreclr/src/gc/vxsort/isa_detection.cpp
src/coreclr/src/gc/vxsort/machine_traits.avx2.cpp
src/coreclr/src/gc/vxsort/machine_traits.avx2.h
src/coreclr/src/gc/vxsort/machine_traits.avx512.h
src/coreclr/src/gc/vxsort/machine_traits.h
src/coreclr/src/gc/vxsort/packer.h
src/coreclr/src/gc/vxsort/smallsort/avx2_load_mask_tables.cpp [new file with mode: 0644]
src/coreclr/src/gc/vxsort/smallsort/bitonic_sort.AVX2.int32_t.generated.cpp
src/coreclr/src/gc/vxsort/smallsort/bitonic_sort.AVX2.int32_t.generated.h
src/coreclr/src/gc/vxsort/smallsort/bitonic_sort.AVX2.int64_t.generated.cpp
src/coreclr/src/gc/vxsort/smallsort/bitonic_sort.AVX2.int64_t.generated.h
src/coreclr/src/gc/vxsort/smallsort/bitonic_sort.AVX512.int32_t.generated.cpp
src/coreclr/src/gc/vxsort/smallsort/bitonic_sort.AVX512.int32_t.generated.h
src/coreclr/src/gc/vxsort/smallsort/bitonic_sort.AVX512.int64_t.generated.cpp
src/coreclr/src/gc/vxsort/smallsort/bitonic_sort.AVX512.int64_t.generated.h
src/coreclr/src/gc/vxsort/smallsort/bitonic_sort.h
src/coreclr/src/gc/vxsort/smallsort/codegen/avx2.py
src/coreclr/src/gc/vxsort/smallsort/codegen/avx512.py
src/coreclr/src/gc/vxsort/smallsort/codegen/bitonic_gen.py
src/coreclr/src/gc/vxsort/vxsort.h
src/coreclr/src/gc/vxsort/vxsort_targets_enable_avx512.h
src/coreclr/src/vm/CMakeLists.txt