thxg

no profile record

Submissions

Exploiting Undefined Behavior in C/C++: A Study on the Performance Impact

2 pointsby thxgvorig jaar0 comments

Notes on Fast Fourier Transforms for Implementers

fgiesen.wordpress.com

95 pointsby thxg3 jaar geleden5 comments

GCC bug #323 (third oldest unresolved bug) is about to get fixed

10 pointsby thxg3 jaar geleden3 comments

comments

5 maanden geledendiscuss

The original Wordle came with a pre-baked ordered list of 2315 "secret" words, off which the daily secret word was looked up (I think based on local time). The list was right there in the javascript code of the game (alongside the list of 12972 allowed guess words). It covered dates from 2021-06-19 to 2027-10-20.

Then in January 2022, the NYT bought Wordle, and started tweaking both lists, first shrinking the secret word list to 2309 entries, but leaving the logic otherwise intact. Fast forward to today, I looked up the current code [1], and it seems that there are now 14855 allowed words. The first 12546 are ordered alphabetically (0: "aahed", 12545: "zymic"), and the next 2309 are not. This may suggest that the latter are the secret words, but the logic for picking them has changed: I found no obvious sequence, when compared to the last few days' secret words. So it's either a more complex sequence, or the secret word is picked server-side.

In any case, I guess they decided to re-shuffle the list now at day 1689 / 2309 in order to avoid giving particularly assiduous player an additional bit of information: they can exclude all previous secret words. (To be accurate, I think this would be 1.897 bits, but my information theory is rusty.)

[1] https://www.nytimes.com/games-assets/v2/9003.896ec900f2a1ce8...

2 jaar geledendiscuss

Indeed those are the "big four" solver businesses in the West, and also probably the most reliably-good solvers. But by the time Gurobi withdrew from the benchmarks (a few weeks ago), COpt was handily beating them in the LP benchmarks, and closing down on them in MIP benchmarks. Solver devs like to accuse each other of gaming benchmarks, but I'm not convinced anyone is outright cheating right now. Plus, all solver companies have poached quite a bit from each other since cplex lost all its devs, which probably equalizes the playing field. So overall, I think Mittelmann benchmarks still provide a good rough estimate of where the SOTA is.

2 jaar geledendiscuss

Regarding presolve: When they test their solver "with presolve", they use Gurobi's presolve as a preprocessing step, then run their solver on the output. To be clear, this is perfectly fair, but from the perspective of "can I switch over from the solver I'm currently using", this is a big caveat.

They indeed report being 5x slower than Gurobi at 1e-8 precision on Mittelmann instances, which is great. Then again, Mittelmann himself reports them as 15x off COpt, even when allowed to do 1e-4. This is perfectly explainable (COpt is great at benchmarks; there is the presolve issue above; the Mittelmann instance set is a moving target), but I would regard the latter number as more useful from a practitioner's perspective.

This is not to diminish PDLP's usefulness. If you have a huge instance, it may be your only option!

2 jaar geledendiscuss

I agree that their results are impressive. Just to be clear, however:

1. They compare their solver with a 1e-4 error tolerance to Gurobi with 1e-6. This may seem like a detail, but in the context of how typical LPs are formulated, this is a big difference. They have to do things this way because their solver simply isn't able to reach better accuracy (meanwhile, you can ask Gurobi for 1e-9, and it will happily comply in most cases).

2. They disable presolve, which is 100% reasonable in a scientific paper (makes things more reproducible, gives a better idea of what the solver actually does). If you look at their results to evaluate which solver you should use, though, the results will be misleading, because presolve is a huge part of what makes SOTA solvers fast.

2 jaar geledendiscuss

I think it's partially excusable. Most LP solvers target large-scale instances, but instances that still fit in RAM. Think single-digit millions of variables and constraints, maybe a billion nonzeros at most. PDLP is not designed for this type of instances and gets trounced by the best solvers at this game [1]: more than 15x slower (shifted geometric mean) while being 100x less accurate (1e-4 tolerances when other solvers work with 1e-6).

PDLP is targeted at instances for which factorizations won't fit in memory. I think their idea for now is to give acceptable solutions for gigantic instances when other solvers crash.

[1] https://plato.asu.edu/ftp/lpfeas.html

3 jaar geledendiscuss

The article is very recent (September 2023 [1]), mentions that "rax is used to return integer values" in the SysV ABI (hence implicitly the 64-bit SysV ABI). Also confirmed in this excerpt:

> Note that the top 56 bits in rax are not zeroed – they contain junk. This is fine b/c the compiler will only make callers check the lowest bit of a register for boolean operations. This is why changing the compiler’s “understanding” (ie the cast) is necessary.

... and yet, the function ABI is clearly i386 (fetching arguments from stack) and indeed everything is compiled with -m32 [2] (i.e. 32-bit SysV ABI). This is a strange contradiction in 2023. On the Intel/AMD side, x86_64 has been prevalent (and the default) for... more than 15 years?

It does not invalidate the article's point. But it is slightly confusing....

[1] https://dxuuu.xyz/

[2] https://godbolt.org/z/ff8r44nKn

3 jaar geledendiscuss

This representation of jagged array is literally the "Compressed Sparse Row" (CSR) format for sparse matrices [1]:

- a single array of floats with all the nonzero matrix entries, ordered row-by-row:

  double values[nnz];

- a single array of ints with the corresponding column index:

  int columns[nnz];

- a single array of ints, of length (m+1), with the start of each row in the two other arrays (the (m+1)th element stores nnz, which will be useful later):

  int start[m + 1];

So to print a whole matrix, you do this:

  for (int i = 0; i < m; i++) {
    index = start[i]; // where
    count = start[i + 1] - start[i]; // number of nonzeros in row i
    
    for (int t = 0; t < count; t++) {
       j = columns[index + t];
       v = values[index + t];
       printf("element (%d, %d) has value %g\n", i, j, v);
    }

To a modern programmer, this may look very old-fashioned (Fortran-ish), but I have tried many alternatives (like grouping columns and values together in a struct, or using pointers), and in my numerical codes, nothing gets even close in terms of performance. It must be said that CSR and CSC (its transpose) are very compact in memory, which is often a bottleneck. Also, since so many sparse numerical codes in benchmarks have used this representation for decades, it could be that CPU designers make sure that it works well.

[1] https://en.wikipedia.org/wiki/Sparse_matrix#Compressed_spars...

3 jaar geledendiscuss

Ligatures are an interesting contrast to Julia programmers' habit of using actual (non-Latin) Unicode characters in their code. It seemed to me that the use of Greek letters and symbols is actively encouraged in the Julia documentation. I think they advise using editors that allow inputting special characters through their LaTeX equivalent (but source files are then saved to disk with the Unicode characters).

I am not very familiar with the latest trends, could anyone else chime in here? Do Julia coders use fonts with ligatures? That could indeed be one case where confusion is possible. Or maybe not?

3 jaar geledendiscuss

MemComputing mainly present themselves as optimizers: Their machine can solve real optimization problems, in practice, today. This is very good because, through that lens, we can skip the BS and go straight to the facts. The evaluation criteria for any optimization approach/algorithm are:

- the quality of the solutions found (in the best case: optimal solutions)

- the presence or absence of optimality guarantees (for example, some algorithms provide optimal solutions very often, but cannot guarantee it 100%)

- the time (or computational cost) needed to find such solutions

Furthermore, the state-of-the-art (SOTA) is well known for most types of optimization problems. In this article, they present a list of real and practical applications, so let us have a look at them one by one:

1.1 Traffic flow optimization

Simple flow problems can be solved in polynomial time (and quickly in practice), so there is no need for anything fancy. Once you introduce additional constraints or discrete variable, the SOTA is mixed-integer programming for offline problems. For online problems it's more complicated. In both cases, I am not aware of any application in which MemComputing can reach SOTA.

1.2 Vehicle routing & scheduling

Here, depending on your computing time constraints, needs for solution quality and/or optimality guarantees, the SOTA can be constraint programming (gecode, OptaPlanner), local search heuristics (LocalSolver), or mixed-integer programming (CPLEX/XPress/Gurobi) with column generation. MemComputing is nowhere to be seen again.

1.3 Supply chain optimization

This is a very broad field, but in general mixed-integer programming is king here.

2.1 Protein folding

Here there is quite an objective measure: the biennal CASP competition. This is where AlphaFold made a splash in 2022. MemComputing has never participated.

2.2 Genome sequencing

I am not knowledgeable enough to comment here.

2.3 Radiotherapy treatment

I am not very knowledgeable here either, but last I looked mixed-integer programming approaches were favored.

3.1 Portfolio risk optimization

Various types of branch-and-bound solvers. Mixed-integer linear/quadratic/convex programming. No MemComputing.

3.2 Detecting market instabilities

No idea.

3.3 Optimizing trading trajectories

No idea.

4.1 Training neural networks

Many people here know how this is done. Stochastic gradient descent on GPUs or TPUs. No MemComputing involved. How can they even claim to be active in this field?

4.2 Detecting statistical anomalies

Vague.

4.3 Classifying unstructured datasets

No idea.

The problem is that if you invent a new optimization algorithm, it is very easy to find one instance of one problem for which your algorithm works well. They did literally that in a paper [1]: They took a library of mixed-integer programming problem instances containing 270 benchmark problems, and published a whitepaper showing that they beat a SOTA solver on one of them. A single instance out of 270!

The really hard part is the opposite: given a class of problems, find an algorithm that beats the SOTA. MemComputing has never done that. Combined with their propensity for grand claims backed by misleading evidence, MemComputing have accumulated a lot of badwill from the academic community over the years. My suspicion is that, while on the surface this post seems to put their approach in contrast to quantum computing, what they really try to do here is ride on the quantum computing hype wave.

[1] https://arxiv.org/abs/2003.10644

3 jaar geledendiscuss

The scientific article seems to be open access [1].

Before people draw links to recent large language model breakthroughs: Although they do use techniques from computational linguistics, there are no neural networks involved. This is more like old-school AI.

They have essentially a giant optimization problem, and they (approximately) model it as a lattice parsing problem, with a stochastic context-free grammar. They can solve that to optimality in O(n^3), which is too slow for some applications. So they propose a O(n) heuristic (hence no optimality guarantees, but the model was approximate to begin with anyways, and the heuristic is a lot faster), which is the reason for the name of their code: "LinearDesign".

[1] https://www.nature.com/articles/s41586-023-06127-z

3 jaar geledendiscuss

The video link in the article works in Chrome but not Firefox mobile (for some reason I can't comprehend).

Working link in case you are interested:

https://www.youtube.com/watch?v=ujjkbLZETHs

3 jaar geledendiscuss

> The best-known algorithms for NP-complete problems are essentially searching for a solution from all possible answers. The traveling salesman problem on a graph of a few hundred points would take years to run on a supercomputer.

This shortcut in explaining NP-completeness is frustratingly widespread. It is also very wrong. A 49-city TSP was solved (to provable optimality) by hand by 1954 [1]. Concorde [2] can solve TSP instances with more than a hundred thousand cities [3]. In practice, for a graph with a few hundred points, you will most likely find an optimal tour in minutes on an iPhone (yes, there is an app for that [4]).

And it's not just about TSP. SATs [5] and MIPs [6] with hundreds of thousands of variables are solved every day to provable optimality. How? Well, sure, the best-known algorithms for NP-complete problems are of course exponential in the worst-case. But they are definitely not "essentially searching for a solution from all possible answers", that would indeed be prohibitively costly. We have algorithms that perform much better on practical instances (dynamic programming, backtracking, branch-and-bound, etc.).

[1] https://www.math.uwaterloo.ca/tsp/uk/history.html

[2] https://www.math.uwaterloo.ca/tsp/concorde/index.html

[3] https://www.math.uwaterloo.ca/tsp/star/about.html

[4] https://apps.apple.com/us/app/concorde-tsp/id498366515

[5] http://www.satcompetition.org/

[6] http://plato.asu.edu/ftp/milp.html

3 jaar geledendiscuss

OP crafts a bmp file in paint, which when renamed to `.bat` runs the command that opens a shell window (cute!).

I don't have access to a Windows machine, but isn't it possible to achieve the same by writing `cmd.exe` directly to a text file in Notepad? Or is Notepad typically off limits as well in such locked down systems?

3 jaar geledendiscuss

> Ah yes, portability.

On Linux it can be argued that CLOCK_MONOTONIC_RAW should be used for durations. From the Linux man page:

       CLOCK_MONOTONIC_RAW (since Linux 2.6.28; Linux-specific)
              Similar  to CLOCK_MONOTONIC, but provides access to
              a raw hardware-based time that is  not  subject  to
              NTP adjustments or the incremental adjustments per‐
              formed by adjtime(3).  This clock  does  not  count
              time that the system is suspended.

There is also CLOCK_BOOTTIME to keep counting time while suspended:

       CLOCK_BOOTTIME (since Linux 2.6.39; Linux-specific)
              A  nonsettable  system-wide clock that is identical
              to CLOCK_MONOTONIC, except that  it  also  includes
              any time that the system is suspended.  This allows
              applications to get a suspend-aware monotonic clock
              without  having  to  deal with the complications of
              CLOCK_REALTIME, which may have  discontinuities  if
              the  time is changed using settimeofday(2) or simi‐
              lar.

3 jaar geledendiscuss

> How does it deal with dust from a household environment?

At 5:55 the interviewee claims that the high back pressure allows them to blow the air through IP68 filter material. It seems dust-proofing is one of their marketing points.

I don't know what to make of this, so just a few random points: The interviewee is actually the founder and CEO. Has a CS PhD from UT Dallas and mostly a high-level management carreer, most lately VP at Qualcomm. They just came out from stealth mode (December) and announced they raised $100M [1].

[1] https://www.nasdaq.com/articles/frore-systems-emerges-from-s...

3 jaar geledendiscuss

Examples on Compiler Explorer:

By default, GCC generates FMA instructions on Haswell and later:

https://godbolt.org/z/GKb7G4nW9

but it does not with -std=c99 on the command line:

https://godbolt.org/z/KTnqcT6aW

Similarly on 32-bit x86, floating-point uses x87 by default, and some intermediate calculations are in 80-bit arithmetic:

https://godbolt.org/z/4q31oEe14

With -std=c99 instead, we can see additional load/stores, which round down results to 64 bits:

https://godbolt.org/z/qdf4hceca

3 jaar geledendiscuss

The bug is about two related floating-point concepts: contraction and excess precision.

The C and C++ standards mandate that floating-point operations follow the IEEE-754 spec. For example, the result of any elementary operation (+, -, *, /) must be the floating-point number "closest" to the exact result of the operation, for some definition of "closest" (i.e., according to a user-modifiable rounding mode). If we denote this rounding operation by fp64(), then the C code

    double x = a + b

results in

    x := fp64(a + b)

Furthermore, the C code

    double y = a + b * c

results in

    y := fp64(a + fp64(b * c))

These restrictive definitions have the huge advantage of allowing portability and determinism of floating-point operations: regardless of the platform, architecture, or compiler, the values of x and y are mandated down to the bit representation. Also, this most often does not come at any performance cost, since most architectures have IEEE-754-compliant instructions.

But then, there are exceptions. For example, the old x87 FPU instructions would allow one to do:

    y := fp64(a + fp80(b * c))

where fp80() uses the internal 80-bit x87 FPU registers. This is "excess precision" (80 instead of 64 bits), and this would generally be faster than the standard-compliant code. A more recent example, since Haswell, Intel CPUs have builtin fused multiply-add (FMA) instructions, allowing one to eschew the inner rounding altogether:

    y := fp64(a + b * c)

This is a case of "contraction" in GCC parlance, and it is also generally slightly faster that the standard-compliant code.

Both "excess precision" and "contraction" seem like win-wins: more accuracy and more performance. However, since we cannot not control exactly when the compiler applies them and when it does not, it comes at the cost of portability / determinism / reproducibility. Even just a compiler version change could give you (slightly) different results.

By default (in "GNU" mode), GCC enables both excess precision and contraction. However, in C, it now exposes command-line options to disable them. Also, specifying a standard (e.g. -std=c99) disables them both. However, no such option existed in C++. From the man page:

    -fexcess-precision=standard is not implemented for languages other than C.

The commit linked in the bug report adds the options for C++.*

3 jaar geledendiscuss

Indeed GCC does not enable -ffast-math by default. Unfortunately, -ffast-math and -funsafe-math-optimizations (despite the name) are not the only options that prevent bit-for-bit-reproducible floating point. For example, -ffp-contract=fast is enabled by default [1], and it will lead to different floating-point roundings: Compare [2] which generates an FMA instruction, to [3] when -std=c99 is specified. As another example, -fexcess-precision=fast is also enabled by default. Similarly, [4] does intermediate calculations in the 80-bit x87 registers, while [5] has additional loads and stores to reduce the precision of intermediate results to 64 bits. In both examples, GCC generates code that does not conform to IEEE-754, unless -std=c99 is specified.

[1] From the man page:

    -ffp-contract=style
           -ffp-contract=off disables floating-point expression
           contraction.  -ffp-contract=fast enables floating-point
           expression contraction such as forming of fused multiply-
           add operations if the target has native support for them.
           -ffp-contract=on enables floating-point expression
           contraction if allowed by the language standard.  This is
           currently not implemented and treated equal to
           -ffp-contract=off.
           
           The default is -ffp-contract=fast.

[2] https://godbolt.org/z/GKb7G4nW9

[3] https://godbolt.org/z/KTnqcT6aW

[4] https://godbolt.org/z/4q31oEe14

[5] https://godbolt.org/z/qdf4hceca

4 jaar geledendiscuss

> It is pretty crazy imho that gcc defaults to using fma

Yes! Different people can make different performance-vs-correctness trade-offs, but I also think reproducible-by-default would be better.

Fortunately, specifying a proper standard (e.g. -std=c99 or -std=c++11) implies -ffp-contract=off. I guess specifying such a standard is probably a good idea independently when we care about reproducibility.

Edit: Thinking about it, it the days of 80-bit x87 FPUs, strictly following the standard (specifically, always rounding to 64 bits after every operation) may have been prohibitively expensive. This may explain gcc's GNU mode defaulting to -ffast-math.

4 jaar geledendiscuss

Yes, and this is not just a theoretical concern: There was an article here [1] in 2021 claiming that Apple M1's FMA implementation had "flaws". There was actually no such flaw. Instead, the author was caught off guard by the very phenomenon you are describing.

[1] https://news.ycombinator.com/item?id=27880461