sparse Multilevel_MQ_Clustering_establish: replace linked-list with generic list
Linked-lists are a common option for implementing dynamic arrays in C. However
on contemporary platforms they have poor performance characteristics. The need
to allocate on every element addition and the pointer chasing involved in
traversing the list pollutes caches and degrades branch prediction.
This change swaps the use of a linked-list for a contiguous array that is
expanded on demand in the manner of C++’s `std::vector`. Traversal is cheap and
the amortized element addition cost is low.
The previous code prepended to linked-lists and then traversed them from
beginning to end. The new code flips this and appends to the lists and then
traverses them from end to beginning in order to preserve the ordering.
While making this change, we also replace the use of a common/memory.h
allocation wrapper with a cgraph/alloc.h one.
Qt6 no longer ships with pkg-config (.pc) file(s). So we need to do manual
discovery of the necessary information ourselves.
QMake is called `qtmake6` in Qt6 and the `qtmake` that ships with it is a
symlink to the former. So this change preferences Qt6 if both Qt5 and Qt6 are
installed.
Some notable warts:
1. Discovery uses `AC_CHECK_FILE` rather than
`AC_CHECK_HEADER`/`AC_CHECK_HEADERS`. The latter seems to exclusively call
the C compiler rather than the C++ compiler, and thus cannot be used for
C++ header discovery.¹ A consequence of this choice is that discovery
checks existence only, not whether the headers are usable.
2. Library discovery also uses `AC_CHECK_FILE` rather than `AC_CHECK_LIB`.
Given the above restriction, if we cannot call the C++ compiler, there is
little point in attempting a link check. But this does mean that discovery
here also only checks existence, not whether the libraries are usable.
3. There seems to be no pkg-config-like mechanism for discovering that e.g.
Qt6Widgets and Qt6PrintSupport depend on Qt6Gui and thus `-lQt6Gui.so` must
also be included in the link line. Qt6 has migrated to a CMake-based build
system and their answer to most of these such problems appears to be “move
to CMake.”² This change just hard codes the link lines under the assumption
these will be stable across the Qt6 series.
4. Qt6 requires C++17,³ so we need to switch from C++11 to C++17 mode when
`--with-qt=yes`. The CMake discovery apparently does this automatically.
5. The `QT_SELECT` environment variable does nothing in Qt6. The line using it
in cmd/gvedit/Makefile.am has been left unchanged in this commit. When
using Qt5 it still avoids accidentally picking up Qt4 and when using Qt6 it
is a no-op.
Gitlab: closes #2233
¹ If accurate, this would also explain the difficulty I had in
https://gitlab.com/graphviz/graphviz/-/issues/1835#note_794857735.
² https://www.qt.io/blog/qt-6-build-system
https://doc.qt.io/qt-6/qt6-buildsystem.html
³ https://www.qt.io/blog/2019/08/07/technical-vision-qt-6
https://www.qt.io/blog/qt-6.0-released
Autotools: import C++17 macro from Autoconf archive
This commit imports m4/ax_cxx_compile_stdcxx_17.m4 from commit da89908ef7d82a90fe5dab8904a65869b5a5d996 of
git://git.savannah.gnu.org/autoconf-archive.git. It will be used in an upcoming
change.
Making this a `double` seems to have been a mistake. Only `int` values are ever
stored into this field and it is only ever compared against `int` values.
Autotools: discover libANN manually if ann.pc is missing
On Debian and Debian derivatives (e.g. Ubuntu) the libann and libann-dev
packages ship without an ann.pc file to support `pkg-config`. As a result of
this, `pkg-config` cannot find libANN and concludes it is not installed.
This change teaches the Autotools build system how to discover libANN manually
if the `pkg-config` technique fails. Note that we need to use `AC_CHECK_FILE`
instead of `AC_CHECK_HEADER` because libANN is in C++.
Similar to the prior situation with Windows platforms, the CMake build on macOS
was failing the long chain test due to insufficient stack reservation. This
change applies the same increase there. Note that there is no need to adjust the
Autotools build, which seems to handle this test case fine on all platforms.
This repairs the long chain test after it was previously inadvertently broken.
Technically going to 32MB is not necessary on all platforms; in release mode,
the MS Build built Graphviz can handle this example with only a 16MB stack. But
it seems simpler to uniformly go to 32MB on all Windows platforms. In a 64-bit
address space, 32MB is trivial and we could even adjust this limit higher in
future. Note that this is the reserved size, not the committed size.
fdpgen mkClusters: use cgraph wrappers for allocation
The lib/cgraph/alloc.h wrappers are similar to the older lib/common/memory.h
wrappers except (1) they are header-only and (2) they live in a directory
(cgraph) that is at the root of the dependency tree. The long term plan is to
replace all use of lib/common/memory.h with lib/cgraph/alloc.h.
fdpgen deriveGraph: use cgraph wrapper for allocation
The lib/cgraph/alloc.h wrappers are similar to the older lib/common/memory.h
wrappers except (1) they are header-only and (2) they live in a directory
(cgraph) that is at the root of the dependency tree. The long term plan is to
replace all use of lib/common/memory.h with lib/cgraph/alloc.h.
Without tracing the code, it was challenging to see that `K2` was always being
set consistently to evaluate to `K * K`. We can remove this complexity by
simply removing the parameter entirely and computing it on-demand.
Without tracing the code, it was challenging to see that `Ht2` was always being
set consistently to evaluate to `Ht * Ht`. We can remove this complexity by
simply removing the parameter entirely and computing it on-demand.
Without tracing the code, it was challenging to see that `Wd2` was always being
set consistently to evaluate to `Wd * Wd`. We can remove this complexity by
simply removing the parameter entirely and computing it on-demand.
This parameter was only being set conditionally, based on whether `useGrid` was
set, making it look as if the incorrect default value of `0` was being used in
some cases. By tracing the code, it was possible to see the only usage of
`T_Cell2` was under exactly the same conditions as which it was set, making the
use safe. We can remove this complexity by simply removing the parameter
entirely and computing it on-demand.
When hitting either of the error conditions in the loop, the next iteration
would be begun without clearing or freeing the object list. The next call to
`objectList` would overwrite the still-allocated previous object list and it
would be lost.
circogen circomps: use cgraph wrapper for allocation
The lib/cgraph/alloc.h wrappers are similar to the older lib/common/memory.h
wrappers except (1) they are header-only and (2) they live in a directory
(cgraph) that is at the root of the dependency tree. The long term plan is to
replace all use of lib/common/memory.h with lib/cgraph/alloc.h.
circogen: replace CDT 'deglist' with a generic list
Apart from de-duplicating some code, this has the following notable effects:
1. The list of nodes is now stored as a contiguous array rather than a linked
list, improving performance characteristics.
2. The list no longer stores degrees, only node pointers. While the code using
this list does modify node degrees, it does not seem to modify the degree
of any node while it is present in the list. So looking up a node’s degree
through the node itself saves some memory overhead.
3. Nodes are inserted into the list and _then_ the list is sorted, rather than
maintaining an always-sorted list. This is a slight performance
improvement.
4. The list is sorted by degree _descending_ now instead of ascending. This
enables operating on the list as a stack, making the pop operation more
efficient.
Using `circo -Tsvg -o /dev/null swedish-flag.dot` on the example attached to
#1718, we have the following:
cgraph: add remove-by-value functionality to the generic list
Note that this assumes elements can be compared using `memcmp` which is not true
for most aggregates. It is the responsibility of the caller to avoid using this
with types that cannot be compared in this way.
cgraph: add sorting functionality to the generic list
Note that this implementation needed to guard the call to `qsort` with a check
that the list is non-empty. UBSan considers passing `NULL` as the first
parameter to `qsort` undefined behavior, even when `nmemb` is 0. I do not know
why this is. I cannot find any text in `qsort` references or ISO C99 to justify
this. But it is simple enough to avoid.
Similarly, passing 0 as `size` causes out-of-bounds accesses in Glibc’s `qsort`.
It is possible there is some text in ISO C99 regarding sizes that indirectly
implies this value must be non-zero. For this implementation, we rely on this
macro never being instantiated with a 0-sized type. It is possible 0-sized types
themselves are impossible without C++’s Empty Base Optimization. I only stumbled
across this quirk of `qsort` by accidentally swapping the `size` and `nmemb`
parameters.
sparse get_or_alloc_force_qt: use cgraph wrapper for allocation
The lib/cgraph/alloc.h wrappers are similar to the older lib/common/memory.h
wrappers except (1) they are header-only and (2) they live in a directory
(cgraph) that is at the root of the dependency tree. The long term plan is to
replace all use of lib/common/memory.h with lib/cgraph/alloc.h.
projects / graphviz / log