Different results of constexpr function during runtime vs compile time

Question

I have this code below that recursively traverses the nodes of a graph (for simplicity, only the edges are shown here). I would expect the result of the count_dfs() function to be 4 regardless of whether the function is evaluated at runtime or compile time.

On MVSC this isn't the case. It works as expected on Clang and gcc, so I'd assume this is a bug in MSVC. Or is there some UB in the code? A far as I know, UB isn't allowed in constant expressions, right? Are there any circumstances under which a function can yield different results in constexpr and non-constexpr execution?

#include <iostream>
#include <ranges>
#include <array>

struct Edge
{
  int from{};
  int to{};
};

constexpr auto node_input_edges(auto& edges, int id)
{
  return edges | std::views::filter([id](const Edge& e) { return e.to == id; });
}

constexpr void visit_dfs(auto& edges, int curr_node, auto func)
{
  for (auto e : node_input_edges(edges, curr_node)) {
    visit_dfs(edges, e.from, func);
  }
  func();
}

constexpr auto count_dfs()
{
  std::array<Edge, 3> edges{{{0,2}, {1,2}, {2,3}}};
  size_t sz = 0;

  visit_dfs(edges, int(edges.size()), [&]()  {
    ++sz;
  });
  return sz;
}

int main()
{
  constexpr auto cnt_ct = count_dfs();
  auto cnt_rt = count_dfs();

  std::cout << "COMPILE TIME " << cnt_ct << "\n";  // 3 on MSVC, 4 on clang and gcc
  std::cout << "RUNTIME " << cnt_rt << "\n"; // 4 on all compilers
  return 0;
}

Compiler explorer

Nelfeal · Accepted Answer · 2022-10-16 19:46:02Z

2

It looks like an issue with how MSVC treats views. Here is a somewhat ugly but equivalent code that works without views:

#include <iostream>
#include <ranges>
#include <array>

struct Edge
{
  int from{};
  int to{};
};

template<std::size_t n>
constexpr auto node_input_edges(std::array<Edge, n> const& edges, int id)
{
    std::array<Edge, n> edges_copy;
    auto j = 0;
    for (auto i = 0; i < n; ++i) {
        if (edges[i].to == id) {
            edges_copy[j] = edges[i];
            ++j;
        }
    }
    if (j != n) {
        edges_copy[j] = {0, 0}; // similar to a null terminator
    }
    return edges_copy;
}

constexpr void visit_dfs(auto const& edges, int curr_node, auto func)
{
  for (auto const& e : node_input_edges(edges, curr_node)) {
    if (e.from == 0 && e.to == 0) { // check for the null terminator
      break;
    }
    visit_dfs(edges, e.from, func);
  }
  func();
}

constexpr auto count_dfs()
{
  std::array<Edge, 3> edges{{{0,2}, {1,2}, {2,3}}};
  size_t sz = 0;

  visit_dfs(edges, 3, [&]()  {
    ++sz;
  });
  return sz;
}

int main()
{
  constexpr auto cnt_ct = count_dfs();
  auto cnt_rt = count_dfs();

  std::cout << "COMPILE TIME " << cnt_ct << "\n";
  std::cout << "RUNTIME " << cnt_rt << "\n";
  return 0;
}

Demo

edited Oct 16, 2022 at 19:46

answered Oct 16, 2022 at 19:40

Nelfeal

13.3k1 gold badge23 silver badges42 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

florestan Over a year ago

Thanks for your answer. I was already investigating a similar approach, but somehow it worked only in the toy example, but not in the real code. Yours seems to work there, too.

Nelfeal Over a year ago

@florestan This null terminator thing is just for the example; in real code I would probably try to mimic what views::filter does (and use that only for MSVC), but I'm not familiar enough with the ranges library to do that here.

florestan Over a year ago

I'm actually using a static vector (basically a std::array along with a size variable) as data structure, so I tried and copied the matching edges into it. That approach gave the correct results on gcc and clang, but again failed on MSVC, interestingly, with a different result than the views::filter...

florestan Over a year ago

So, after digging a bit deeper, it turned out, that the problem is in the range based for loop. If I iterate through the range using iterators, it works as expected: godbolt.org/z/jTbT6rdxT

Nelfeal Over a year ago

@florestan That's interesting, though I assume it's an issue with the combination of views and range-based for loop, because range-based for loops have been around for a long time now. There seems to be caching going on in MSVC's filter_view; perhaps that's it. I'm not going to look further into it, after all it's just a bug and you seem to have a good workaround.

Collectives™ on Stack Overflow

Different results of constexpr function during runtime vs compile time

1 Answer 1

5 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

5 Comments

Your Answer

Sign up or log in

Post as a guest

Related