Discrepancy between memory_fits(...) and memory_usage(...)
#527
Comments
|
@nhusung what version of Adiar/BDD Benchmarks are you using?
I do use Linux 6.5 and GCC v13.2, so it might also be a weird difference between the compilers. Just to be sure, can you try some of the following things for me, please?
|
SSoelvsten
changed the title
memory_fits(...) and memory_usage(...)
|
I’m using the latest Adiar version ( However, when compiling with GCC 13.2.1, the benchmark runs fine. |
|
Thanks for confirming it is a compiler-specific issue. I do not believe it makes Adiar use more memory than it is given (if it does, you'll get a warning) so if you need something quick, you should just comment out this line (or compile with The Clang-specific fix will take me some time to dig through. |
|
No, building in Release mode does not fix the problem. The problem occurs in release mode only. (I used Edit: This is not a severe problem for my benchmarks; I can simply use GCC-compiled binaries for Adiar. I just experienced severe performance issues with Sylvan when using GCC-compiled binaries. I have not analyzed that problem yet. I just thought that the comparison would be fairer when using the same compiler for all packages. I also was not able to build the |
|
It definitely would be the best if you can compare them with the same compiler. If I were you, I would just remove said line of Adiar. The fact that it crashes for Release is an error of mine. It should have been a debug-only statement. This probably shows that I ought to clean up the assertion stuff ( See #422 and now #529 ). Thanks for the hint on Regards to the memory usage computations with Clang, this is something I still have to dig into. |
|
The The memory computations are in a helper class template <typename child_t>
struct linear_memory_base {
static constexpr memory_size_type memory_usage(memory_size_type size) noexcept
{
return static_cast<memory_size_type>(
floor(static_cast<double>(size) * child_t::memory_coefficient()
+ child_t::memory_overhead())
);
}
static constexpr memory_size_type memory_fits(memory_size_type memory) noexcept
{
return static_cast<memory_size_type>(
floor((memory - child_t::memory_overhead()) / child_t::memory_coefficient())
);
}
...
};The template <typename T, typename Allocator = allocator<T> >
class array : public linear_memory_base<array<T> > {
...
static constexpr double memory_coefficient() noexcept
{
return (double)sizeof(T);
}
static constexpr double memory_overhead() noexcept
{
return sizeof(array);
}
...
};There are multiple small things that could be part of the issue
I'll put back on the detective hat and see what I can do. 🤠 From here though, I probably need to install Clang 15 locally on my machine. |
|
Yes, I think you need some version of clang to debug the problem. As I said: I couldn’t observe a fail of this assertion in debug mode. Even in release mode, when inserting a debug print ( Here is the CMake command I used: If you set the environment variable EDIT: I don’t know if the reported errors above are related to this bug. They should be fixed though. Here, the problem seems to be that boost calls the |
|
Hmm, I don't think that is related. I double-checked my |
|
I just “reactivated” the assert by using |
No, no, it’s a TPIE internal thing. It happens during |
|
Line 108 of The problem stems from the const tpie::memory_size_type max_value = std::numeric_limits<tpie::memory_size_type>::max();
const tpie::memory_size_type max_elem = memory_fits(max_value);
if (no_elements > max_elem) {
return max_value;
}
return unsafe_memory_usage(no_elements);Indeed the value 1.84467e+19 is a 64-bit unsigned max value. That is, in your compilation with Clang 15, the input, an intermediate value, or the final result is cast to an unsigned long rather than an unsigned long long as is expected ( |
|
I have created the following unit test in my fork of TPIE which passes with GCC 13 but not Clang 16 on my Fedora 38 machine. bool array_memory_prediction_test() {
...
{ // Test for maximum 'unsigned long long' value
unsigned long long i_mem = std::numeric_limits<unsigned long long>::max();
const memory_size_type size = tpie::array<int>::memory_fits(i_mem);
const memory_size_type o_mem = tpie::array<int>::memory_usage(size);
TEST_ENSURE(o_mem <= i_mem,
"memory_fits() and memory_usage() expected to be their safe inverse");
}
return true;Specifically, I am able to get it to fail with CMake set up as follows In fact, it looks like the build type is relevant to show this issue. If it is not set, then the problem does not occur. Specifically it works fine for values in [64, 1024] but not the maximum value of |
|
I am sadly unable to get ubsan to work on my Fedora machine (I get linker errors, as it tries to find ubsan in an empty directory). I've cleaned up the code on this branch to split the one-liner into four different statements. I was hoping this would allow me to figure out where the cast to unsigned long was. |
|
Yet, with a little binary search I can tell you that the bug does not occur with |
Strange 🤔 I just installed clang etc. in a F38 docker image and UBSan works out of the box. I only have problems with printing the stack trace (possibly related to |
|
So it is either in the call to I probably did something wrong on my end, but I've spent 7 hours trying to fix this - and it's not really worth it. This whole problem is due to me being extremely paranoid about overflows in the first place. Since I primarily use |
UBSan complains about the |
|
I read it the same way too, but knowing that I know very little, I was not personally going to rule out the |
|
The sane way for performing the conversion would probably be something as ugly as: §7.3.10p1 of the (draft of) the C++20 standard explicitly states:
I know Adiar/TPIE too little to know why the approximate values are so large. But undefined behavior must not occur by any means. An allocation larger than An alternative would be
TL;DR: Safe double-to-integer conversions seem to be a mess in C++ |
|
Yes, before the fix in #530 , I tried to safe-guard against I have moved your fix onto the TPIE branch I mentioned above. I'll test later whether it makes the unit test pass. I am unsure whether it will be accepted by the TPIE maintainers, considering that this function is called reasonably often and it fixes a technically unrealistic use-case (if it wasn't for me being a dummy). An alternative fix they might be ok with is to insert an assertion. |
|
Most of all: thanks for all the help and support with tracking down this issue. Your fork includes a lot of good changes to the benchmarking repository. Do you mind if I try to cherry-pick some of these changes (of course trying to keep your authorship of the commit). There are also other things with the benchmarking repository that I really want to fix (the use of Furthermore, looking at your newly added CNF example, one may argue that the There are reasonable arguments to keep it as-is, but you should be warned that Adiar will run surprisingly badly (in a way that arguably is unrepresentative). |
|
First of all, I really have to thank you for all your work here and for fixing the issues so quickly. BDD-Benchmark was a huge timesaver for me, because otherwise I would have had to implement all the adapters and benchmarks on my own. If you can cherry-pick some of the changes I made to BDD-Benchmark, I’d really appreciate it (I also don’t mind should you mess up the authorship). Some time ago I thought that I should probably create pull requests but then I felt like my git history was a bit messed up (e.g. one commit making Cudd’s ZDD implementation fail) and I would need to do some rebasing. Thanks for the hint concerning the CNF benchmark. I didn’t immediately get the sense behind the builder (I haven’t read a lot of Adiar’s docs so far) but I was already suspecting some reason like that. I think I’ll rewrite the function in the near future. I don’t expect the difference to be big, though, since the clauses usually consist of ≤ 10 variables. |
|
Thanks! I'll try to cherry-pick as much of your fixes for CMake and the adapters as I can. That is, assuming I don't run into too much of a merge conflict; otherwise, I might leave it for a reimplementation. Adiar is kind of weird in the sense that it gets faster (per node processed) as inputs and outputs get larger (until disk I/O is the bottle-neck even for Adiar). For tiny instances, there is a major relative performance difference between Adiar and other BDD packages which accumulates. With v1.2 we fixed this as much as is possible without changing the fundamental algorithm. For more information, see our ATVA 2023 paper on the optimisation in v1.2 (the extended paper is available right now on arXiv). You will also notice, that CAL has a jump from being pretty good to much worse around "moderate" instance sizes. This is essentially for the same reason: their breadth-first algorithms are not competitive for small BDDs. Hence, for small inputs (< 219) they switch to the classic depth-first recursive algorithms. In Adiar we do not have such a thing (yet... in #444 I have what I believe to be a good idea that works for Adiar) |
@nhusung tried to use the bdd-benchmark set to compare a new BDD library to existing ones. However, there are problems with Adiar:
Interestingly, they couldn’t observe a fail of this assertion in debug mode. Even in release mode, when inserting a debug print just above the mentioned line, the assert did not fail.
(I’m on Linux 6.4 and use clang 15.0.7)
Originally posted by @nhusung in #388 (comment)
The text was updated successfully, but these errors were encountered: