compile time optimisations

[arturbac]

from discussion on issue #1501
here from example_json

Largest times from instantations (relative to top wall time)

Write insantations

cpp glz::write_json<BasicStruct &, std::basic_string<char> &>
Wall Duration 33,266 ms

Wall Duration	instantation
10,695 ms	cpp glz::reflect<BasicStruct>
6,144 ms	cpp glz::for_each_short_circuit<4UL, (lambda at /home/artur/projects/glaze/include/glaze/core/reflect.hpp:316:39)>
8,386 ms	cpp "glz::detail::invoke_table<4UL, (lambda at /home/artur/projects/glaze/include/glaze/json/write.hpp:1571:35)>"

Read instantations

cpp glz::read_json<BasicStruct, std::basic_string<char> &>
Wall Duration 66,972 ms

---

Wall Duration	instantation
3 x 12,912 ms	cpp glz::detail::front_bytes_hash_info<unsigned short, 4UL>
16,521 ms	cpp glz::detail::unique_per_length_info<std::array<std::basic_string_view<char>, 4>>
5 x ~5,942 ms	cpp glz::detail::decode_index<opts{...}, BasicStruct, 1UL, BasicStruct &, glz::context &, const char *&, const char *&>

where functions front_bytes_hash_info, unique_per_length_info are called for glz::detail::make_keys_info<4UL> which takes 45,007 ms of wall time

[arturbac]

removing span from compile time instantiations and move to pointer + size sometimes can cut time in half. I had to remove span use in consteval in simple enum for that reason (replaced with ptr, size arguemnts to functions)

wall 12,912 ms "glz::detail::front_bytes_hash_info<unsigned short, 4UL>"
where construction of span calling constructor and initialization takes
half of that time
span is build wall 6,479 ms "std::span"
jsut for wall 2,869 ms processing of std::reverse_iterator<__gnu_cxx::__normal_iterator<unsigned long *, std::span>>
So half the time is span and its reverse iterator, which can be just probably --ptr or at least reverse iterator from ptr, size arguments

ex:

const auto bucket = hash % bsize;
               if (contains(std::span{bucket_index.data(), index}, bucket)) {
                  break;
// uses span but can ptr and size
   constexpr bool contains(auto&& data, auto&& val) noexcept
   {
      const auto n = data.size();
      for (size_t i = 0; i < n; ++i) {
         if (data[i] == val) {
            return true;
         }
      }
      return false;
   }

[stephenberry]

Wow! Yeah, because these are known types, I can probably also make a pseudo-span that isn't templated. But, I'd first go for a pointer and size like you suggested.

Feel free to make pull requests for these changes, but I'll also try to do some -ftime-trace optimizations when I'm able.

[stephenberry]

I noticed that using std::vector in compile time code often leads to less template instantiations than using std::array<T, N>, because when algorithms like sort are used there are template instantiations needed for every length N for the array, but the vector doesn't require different instantiations for different sizes.

[arturbac]

vector -> when using own string view without constructors and default init, it does not require initialization at all so array is just a declaration. You are right that this is not true for std::string_view which default initializes all elements.

[arturbac]

You did not answer where to put code of basic_string_view and span, which include ?

[arturbac]

In a lot of cases we need the compile time string_views to propagate to runtime, which is why std::string_view is desired. But, I look forward to seeing the changes you are proposing.

We can add implicit operator std::basic_string_view() to own basic_string_view

[arturbac]

Btw nice is that having string_view which does not initializes elements by default at compile time this works as a strong verification If Your algorithm works as expected, because when not and some element is not initialized and used it generates compile time error.

[stephenberry]

@arturbac

vector -> when using own string view without constructors and default init, it does not require initialization at all so array is just a declaration. You are right that this is not true for std::string_view which default initializes all elements.

I was actually talking about template instantiations and not initialization with std::vector vs std::array.

You did not answer where to put code of basic_string_view and span, which include ?

I would say make includes: glaze/util/string_view.hpp and glaze/util/span.hpp

Btw nice is that having string_view which does not initializes elements by default at compile time this works as a strong verification If Your algorithm works as expected, because when not and some element is not initialized and used it generates compile time error.

Excellent point.

[arturbac]

I understand what You meant with array<,N> but You are wrong with unique_per_length_info
because N is not consteval but const auto N = input_strings.size();

so that why i used this below, btw is this N really need to be any size_t ?
because this is pure consteval and none of Your tests needs more than 128, so maybe we can remove at all vector here ?

      std::vector<string_view> strings_;
      std::array<string_view, 128> stringsa_;
      span<string_view> strings;
      if (N < stringsa_.size()) {
         for (size_t i = 0; i < N; ++i) {
            stringsa_[i].data_ = input_strings[i].data();
            stringsa_[i].size_ = uint32_t(input_strings[i].size());
         }
         strings.data_ = stringsa_.data();
         strings.size_ = N;
      }
      else {
         for (size_t i = 0; i < N; ++i) {
            strings_.emplace_back(string_view{input_strings[i].data(), uint32_t(input_strings[i].size())});
         }
         strings.data_ = strings_.data();
         strings.size_ = strings_.size();
      }

and this comment is wrong
// This could be a std::array, but each length N for std::array causes unique template instaniations

[arturbac]

I think the best approach is probably to use C style arrays that are stack allocated.

I is hard for me to guess how far You want to push on performance here
when using custom span i proposed it gives clear code but has some penalty when using member functions
on the other hand You can remove almost any begin, end, empty etc and achieve higher performance at a cost of unclear code

[stephenberry]

I understand what You meant with array<,N> but You are wrong with unique_per_length_info
because N is not consteval but const auto N = input_strings.size();

You can pass N in via template <size_t N>, which I tested and allowed the use of std::array, but then I was seeing more template instantiations due to std::array of different sizes.

[stephenberry]

I don't think using pointers and sizes is too ugly, especially if you use non-template helper functions. In critical compilation places I'm fine with sacrificing some readability for performance. I'm finishing up a faster to compile sort function.

[stephenberry]

Also, check out https://www.build-bench.com, which can be really helpful for profiling build times of bits of code.

[stephenberry]

@arturbac
I want to make you aware of this active pull request I plan to merge in soon: #1514
This fixes the duplicate to_tuple instantiation that you had brought up. It also moves the tuple class out of the tuplet namespace, which makes the -ftime-trace results a good bit smaller.

[arturbac]

I just think it does not make a sense when I dig out finding issues/potential optimisation places examine how to fix it and then You are faster committing a fix for it.

[stephenberry]

I'm trying to fix the trivial things so that you don't have to change as much code. It's better to solve one thing at a time than everything at once.

[stephenberry]

If you made pull requests for these fixes then I could contribute and help merge them faster.