tmyklebu

Seems like the author is missing a trick?

You can use a simple hash table without probing to classify each number as either (1) first instance of a number in the table, (2) known duplicate of a number in the table, or (3) didn't fit in the table.

If you use a hash table with n buckets and one item per bucket and the input is random, then at least 63% of the distinct numbers in the input will fall into cases 1 or 2 in expectation. Increasing table size or bucket size improves this part of the math.

On really big inputs, it's probably still healthy to do a pass or two of radix sort so that the hash table accesses are cheap.

Well, modular multiplication is faster than modular inverse, both asymptotically for large moduli and practically for almost all moduli I can think of. (2, 3, and 4 being notable exceptions!)

The article computes modular inverses of a_1, ..., a_n by:

- Computing (a_1 * ... * a_i) = (a_1 * ... * a_{i-1}) * a_i recursively

- Computing (a_1 * ... * a_n)^(-1) by square-and-multiply

- Computing (a_1 * ... * a_i)^(-1) = (a_1 * ... * a_{i+1})^(-1) a_{i+1} recursively.

- Computing a_i^(-1) = (a_1 * ... * a_i)^(-1) * (a_1 * ... * a_{i-1}) for each i.

The second step is a scalar operation, so its running time is immaterial as long as you aren't doing something too silly.

For my caveman brain, both Fermat's little theorem and square-and-multiply exponentiation are pretty easy to understand. Moreover, the code is going to be "defect-evident"---if I've gotten the logic wrong or forgotten integer promotions or modular reductions as in qsort's post, it'll quickly be clear by skimming the code.

Yeah, that was just a search.

There are 2^32 multipliers; call them m. For a bit in m*x to be useful, it must be zero for 16 symbols and one for 16 symbols. Call those bits "useful bits." Try every multiplier; for each multiplier, compute all the useful bits (usually not many) and try all masks with 5 useful bits.

Same idea, but without BMI2:

  unsigned h = (1264523 * x & 0x1020a01) * 134746240 >> 27;

Alternatively:

  unsigned h = (1639879 * x & 0x1038040) * 67375104L >> 32 & 31;

The multiplication by 67375104L can be a usual 32x32 IMUL where the high half goes to edx, though I'm not sure that conveys a benefit over a 64x64 IMUL in serial code these days.

Two fast (today) instructions:

  unsigned h = _pext_u32(1264523 * x, 0x1020a01);

The second stage (on-site, ~20 competitors) is done like that.

The first stage (this one, with ballpark 10000 competitors) is distributed and done in very heterogeneous environments, and it relies on local high school teachers taking time out of their day to set up whatever's needed, proctor the contest, and grade the results.

This really is quite sad.

The first stage of the CCC is written in pretty heterogeneous conditions. There are several thousand competitors across the world. Students use a language of their choice and their work is graded by their teacher against a rubric sent out by the contest organisers. I recall that the teacher has to send the work to Waterloo, postmarked within a couple of days after the contest.

Sometime in the summer, the University of Waterloo then flies out and puts up the top 15 or 20 students in that more informal contest to compete in what was the "CCC Stage 2" and is now the "Canadian Computing Olympiad." This second contest is done under more controlled conditions and its results largely determine which four students will represent Canada at the International Olympiad in Informatics.

The first stage has always relied on teachers' honesty. The contest organisers mail contest packets to teachers in advance of the contest. Teachers have some time between contest day and when the results need to be mailed back to Waterloo. Students are comparing notes and discussing the contest immediately after the contest.

Nonetheless, in my experience (more than 15 years ago), all or almost all of the students who make it to the second stage deserved to be there. I hope that continues to be true.

This was a popular topic in '80s linear programming books. Chvatal's "Linear programming," for instance, is carefully-written and devotes about 100 pages devoted to network simplex. Papadimitriou and Stieglitz's "Combinatorial optimization: algorithms and complexity" explicitly goes through primal-dual derivations of algorithms for shortest path, max flow, and min-cost flow (including bipartite matching). I haven't read it in any detail, but https://math.mit.edu/~goemans/PAPERS/book-ch4.pdf is online and might be to your liking.

No cuts are necessary for minimum-weight bipartite matching as the constraint matrix is totally unimodular. Total unimodularity guarantees that any optimal basic solution is an integer solution.

Moreover, well-known algorithms for linear programming like simplex and primal-dual methods have straightforward (and illuminating!) combinatorial interpretations when restricted to minimum-weight bipartite matching.

There are theory papers on "buffer trees"---B-trees where each node is augmented with an O(B)-length array of pending updates and queries. I believe there were also some attempts at building SQL databases based on them. It sounds like you're reaching for the same trick.

This is pretty persnickety and I imagine you're aware of this, but free is a weak symbol on Linux, so user code can replace it at whim. Your foo cannot be statically determined to be UB.

It does something unexpected if size is SIZE_T_MAX-1, too. And it's also undefined if input is null and size is zero, which seems more likely to surprise that function's author. This is because memcpy requires valid pointer arguments even if the size is zero.

In particular, this usage invokes UB:

  const char *input = "";
  size_t len = strlen(input);
  char *buf = malloc(len);  // may return null if len is zero
  if (len) memcpy(buf, input, len);
  char \*buf2 = strappend(buf, len);

(Edited for formatting.)

Compile time is another reason to prefer push_back, which is a function, to emplace_back, which is a function template.

First, what a great resource you've put together! You're presenting a lot of useful material clearly and concisely, together with the reasoning behind it. I wish I had this when I started doing performance work.

> For a perfect drop-in replacement of std::lower_bound, the best you can do without breaking anything is to make the search branchless and maybe add some prefetching [1]. Some compilers actually try to implement std::lower_bound this way, but these things can sometimes break from version to version because there are no semantics to reliably make compiler use predication instead of branching.

What's imperfect about a radix-4 (or higher) search instead of a binary search for replacing std::lower_bound? For a radix-k search, you'll have k-1 fetches in flight before you decide which subarray to recurse on, and your dep chain will be log_2(k) times shorter.

To try to argue it:

Humanity does better when we don't marginalise people for dumb reasons such as membership in a visible minority group. Marginalising someone for a dumb reason is an individual decision, and it's a decision that a professor is frequently in a position to make.

Arguably the higher-leverage parts of a professor's job are teaching classroomfuls students at once, advising graduate students, and "service," meaning things like sitting on committees within the university, attending and sometimes organising conferences, and so forth. These all involve the professor spending time to help others' careers. Owing to their leverage, it's especially important that these aspects are done well. And since candidates for tenure-track jobs generally haven't been in such a position of leverage before, it's especially important to screen for suitability for teaching and service when hiring tenure-track professors.

I'm sure you can polish this, and I'm sure there are other arguments in the same direction.

Regarding specialisation, I gave an example of a world-class researcher who also does outreach to an underrepresented group in the post you replied to.

Moreover, the research, teaching, and service parts of a professor's job aren't as separable as you'd hope---the overarching purpose of it all is to keep a field of academic inquiry alive, where research, teaching, advising, and service all operate at different time scales. The field of a group of researchers who don't teach or advise students dies when they all die. A hypothetical teacher who isn't involved in research can't bring students near research-level work.

Not research, but Jelani Nelson at Berkeley ran programmes in Ethiopia to expose schoolchildren to programming. (In case it needs to be said, Jelani is a top-shelf theoretical computer scientist.)

I wasn't around for too much of the 1980s, but I think there was a qualitatively similar hype cycle starting in the late 1970s.

MINOS, CPLEX, XpressMP, OSL, KORBX, GAMS, AMPL, and many other optimisation packages came out of that period. Those packages were not free software or open-source software, but they were available to researchers at universities in the First World. (It seems unfair to expect software from 1978 to be free software or open-source software as we understand it today given that the FSF dates to 1985 and the term "open-source" to the late 1990s. Also bear in mind that personal computing was in its own initial boom in the 1980s.)

Papadimitrou and Steiglitz's book (published 1982; I have the 1998 Dover edition) has an exercise (Chapter 15, exercise 19) in which you are to read a short 1979 New York Times article about the ellipsoid algorithm and "[d]etermine, where possible, whether each statement is (a) true, (b) false, (c) misleading, [or] (d) equivalent to a well-known conjecture, the solution of which was probably not known to [the article's author]."

There's a longer article written by the same author 20 days earlier, too, and that one has more unfounded speculation about applications of LP: https://www.nytimes.com/1979/11/07/archives/a-soviet-discove...

Karmarkar's 1984 interior-point method begat similar excitement, leading to a few thousand papers through the late 1990s, and a trickle still today, on interior-point algorithms of varying correctness, generality and efficiency.

The technology that came out of that hype cycle is phenomenally capable and usable, and it's subsequently been improved even further.

If you're just looking for hard-to-round inputs, you can also enumerate the double precision space completely with some cleverness and modest patience.

Elkies [0] computes a piecewise linear approximation to his (number-theoretic) function of interest and does a lattice reduction on each piece to filter out the vast majority of the space. The same approach, works almost everywhere on all of the transcendental functions I've tried, and I believe the CRlibm group uses it.

[0] https://arxiv.org/pdf/math/0005139.pdf

Nocedal and Wright is an excellent overview and a good starting point. Also consider:

- R. Schneider, Convex bodies: the Brunn-Minkowski theory. The first two chapters are an excellent introduction to convex geometry (plus a little bit extra!) if you have some undergrad-level analysis.

- Hiriart-Urruty and Lemarechal, Fundamentals of convex analysis. This book has been highly recommended to me but I've never used it. Might be an easier go than Schneider for convex geometry.

- Golub and van Loan, Matrix computations. Excellent book on numerical linear algebra.

- Bonnans, Gilbert, Lemarechal, Sagastizabal, Numerical optimization: theoretical and practical aspects. This book has a detailed description of bundle methods, which are important and in my opinion underutilised.

- I. Maros, Computational techniques of the simplex method. This is the only book I'm aware of that discusses how to build a working implementation of the simplex method for linear optimisation.

I'm not aware of any books that cover line search algorithms in detail. These are important in implementations but, beyond discussing the Goldstein and Wolfe conditions, generally glossed over in prose. Even in the absence of stalling and numerical difficulties, you can see an order of magnitude speedup from replacing a bad line search with a good one. One line search algorithm I've had success with is described in More and Thuente, Line search algorithms with guaranteed sufficient decrease.

Lots of tacit engineering knowledge goes into building a fast and robust optimisation code. Some of that knowledge gets forgotten when code is rewritten or ported from one language to another.

Mercifully, a lot of that engineering knowledge has been encoded into freely-available optimisation code. Quite a bit of that code is pretty readable. Off the top of my head, I've learnt things from:

- Liu and Nocedal's Fortran L-BFGS implementation,

- The CUTEst problem collection,

- Chih-Jen Lin's LIBLINEAR and LIBSVM,

- Lin and More's TRON,

- Csaba Meszaros's BPMPD,

- Jacek Gondzio's HOPDM,

- The GNU Linear Programming Kit,

- and probably quite a few other sources!

What makes you think he misunderstood? What happens on fc30 when you 'yum install dstat' as he suggested?

This webpage listing the contents of the fc30 pcp-system-tools package: https://fedora.pkgs.org/30/fedora-updates-x86_64/pcp-system-...

lists a file called '/usr/bin/dstat'. The pcp-system-tools package obsoletes a package called 'dstat'. If you go to https://pkgs.org/download/dstat, and look under "Fedora 30," you get pcp-system-tools.

[Spoiler: 'yum install dstat' installs pcp-system-tools, which has a symlink /usr/bin/dstat -> /usr/libexec/pcp/bin/pcp-dstat.]

Not exactly what you asked for, but C11 added this bit that was not there in C99:

An iteration statement whose controlling expression is not a constant expression, that performs no input/output operations, does not access volatile objects, and performs no synchronization or atomic operations in its body, controlling expression, or (in the case of a for statement) its expression, may be assumed by the implementation to terminate.

And C++11 added this bit that wasn't there in C++03:

A loop that, outside of the for-init-statement in the case of a for statement, - makes no calls to library I/O functions, and - does not access or modify volatile objects, and - performs no synchronization operations (1.10) or atomic operations (Clause 29) may be assumed by the implementation to terminate.

[Note: This is intended to allow compiler transformations, such as removal of empty loops, even when termination cannot be proven. -- end note]

Threading was a structurally different change from fs operations and networking. You need the compiler to cooperate when you're writing to a location in one thread and reading it from another. You can either get there using hacks built on escape hatches like 'asm volatile' or by specifying some semantics for the operation. Specifying a memory model, however imperfect, means we can move away from the implementation-dependent hacks.

> Example: Sockets should be IN. As above, vast numbers of programs want to use sockets and a standard approach would suit almost all of them perfectly well.

I think the BSD socket library is that standard approach...

Just picking a couple quotes from the article:

> Especially when you compare C++ to other languages, there’s a pretty strong argument to be made for a more inclusive and even all-encompassing standard library - look at the richness of the standard libraries for Java or Python.

What is that argument? And even if you accept that argument, can we execute? That is, will the result be at least of a similar quality, or will it be riddled with subtle gotchas and sharp edges like the existing C++ standard library?

> So, what should go in the standard library? Fundamentals. Things that can only be done with compiler support, or compile-time things that are so subtle that only the standard should be trusted to get it right. Vocabulary. Time, vector, string. Concurrency. Mutex, future, executors.

Can the standard be trusted to get these things right?

- Vocabulary: There's a fair amount of depth to what "right" means for vector and string in many contexts, so the standard can only be trusted to get them "right" in cases that have very few constraints (where it can do admirably). Implementors have been known to break the ABIs of std::vector and/or std::string between compiler/library versions, so they aren't appropriate types to use in interfaces.

- Concurrency: Leaving aside the C++ memory model, the library support should largely be avoided. For an example of why: std::condition_variable's ctor either takes another condvar or no arguments. pthread_cond_init takes a pthread_condattr_t. On Linux, this can specify a clock. On my system, if you want to wait for a second according to CLOCK_MONOTONIC/std::chrono::steady_clock on my implementation, condition_variable::wait_until will convert your time to CLOCK_REALTIME/system_clock (by now()ing both clocks and adding the difference to the deadline you supplied) and sleep until the converted time. That's not what you asked for; it's totally wrong and possibly dangerous.

There's more than enough neat stuff I don't know in there. Unfortunately it's tough to trust a source with so many errors in the stuff I do know.

I wasn't aware of any CLT for iid random variables with infinite variance. Do you have references?

This list is fun, but it's a little bit sloppy:

- The central limit theorem relies on the mean and variance of your random variable existing; there are random variables for which mean and variance don't exist.

- The definition of "measure-preserving" in the ergodic theorem statement is missing the measure.

- dim (ran A)^perp = dim ker A^T can be strengthened by dropping the dim's. If v in ker A^T, then A^T v = 0. Pick any Ax in ran A; then <v, Ax> = <A^T v, x> = <0, x> = 0, so v is in (ran A)^perp.

- Others pointed out that 20 looks busted.

- The definition of Haar measure needs to fix the measure of some nonzero-measure set, or "unique" needs to be replaced with "unique up to scaling" otherwise the theorem isn't true.

- "Sounders Mac Lane"

- 25: x_0 came out of nowhere; it's unclear from the text which "invertible" is meant; the basin of convergence for Newton's method for finding a local continuation can be very small indeed.

- 36: Why is the adjoint of A named T^*?

- 46: You need some assumptions about f.

> The converse is also true (and is much easier to prove, so we won’t be concerned with it): a diagonalizable matrix is always normal.

It is actually more difficult to prove. [2, 1; 0, 1] is diagonalisable (via [1, -sqrt(2)/2; 0, sqrt(2)/2]) but not normal.

It might be instructive for you to try solving the linear programs in netlib[0] with stochastic gradient descent. ;)

The short version of the story is that different optimisation problems have different kinds of structure, and the user will want solutions of different quality and have different amounts of patience depending on the context. Practical optimisation is largely about finding ways to exploit the structure of a problem to get solutions of some quality in some amount of time. No known optimisation algorithm dominates all others.

In many machine learning contexts, you want a low-precision solution to a problem with an objective that's expensive to compute but can be reasonably approximated by random sampling. Often, when you use a linear program solver, you want a solution to a linearly-constrained problem where the geometry of the constraints may not be "easy" and any violation renders a solution completely useless.

Good LP solvers can solve "typical" well-formulated LPs with hundreds of thousands of variables and constraints in a matter of seconds on modern hardware[1]. These algorithms can't solve many of the problems you're going to feed into your deep learning framework at all. Conversely, your deep learning framework will have a hell of a time solving LPs.

As for why GAMS and AMPL are a thing, they're interfaces to solvers, not solvers themselves. You use them because they can handle pulling the data out of the database, translating your GAMS/AMPL program into a formulation suited to the solver you choose, running the solver, and handing back the results. It's straightforward but tedious to do this all on a case-by-case basis; GAMS and AMPL automate much of the uninteresting work.

[0] http://www.netlib.org/lp/ [1] http://plato.asu.edu/ftp/lpcom.html

> What else are you going to do in C? But even most real world implementations of C have all sorts of structs and typedefs that you shouldn’t make any assumptions about and you should treat as an opaque type.

Subtract two times? (BTW, struct tm isn't an opaque type.)

> > Who are you to say I won't do math on account ids?

> Is that really what you are going to argue? That in a real world use case you’re going to be doing math on an accountId?

You seem to think that's absurd? Maybe I want to store a set of accountids. So I sort them (bit-extraction or comparison!), take deltas (subtraction!), and encode the deltas sensibly. Maybe I have two lists of accountids and I want to check that none of the things in the first list show up in the second list. Some sort of hashing scheme (bit-fiddling!) is going to be my friend here.

> > What ORM? What database? If I'm using an ORM and a database, high-performance time operations are likely out of the question.

> So you’re going to pass a raw key/value record set around your code and program like it was 2006? So now you’re going back to mapping your sql resultset to an object that makes sense anyway. Going right back to my point that you’re going to have a mapping between your raw results -> domain model -> view model (where the view model is serialized for external use) and back again anyway.

What SQL? What resultset? What object? I have an integer. Why do you assume it doesn't make sense?

> Even C has a bunch of functions to work with the date struct as an opaque type....

Yes, for conversion to/from time_t, formatting, and parsing. That's my point; you use the integral type whenever you don't care whether it was a Thursday because the integral type isn't going to waste your time.

> And then you use a better class. In Java you use something like JodaTime in .Net you use NodaTime - a .Net library written and maintained by Jon Skeet (the person with the highest ranking on Stack OverFlow). If that’s not good enough you write a custom extension or mixin to handle your special snowflake handling and still let all of the consumers treat it as an opaque type.

Stop with the hero worship. You should do things that make sense in context. Recommending that everyone use a library in all contexts because it's written by Jon Skeet is a ridiculous thing to do. (BTW, it seems like the Joda-Time people recommend you use the standard java.time package instead.)

> We were talking about an accountId that just happens to be represented as an int. You’re not going to be doing math on an account id. Also neither .Net with generics or even C++ templates have the boxing and unboxing issue.

Who are you to say I won't do math on account ids?

> If there was a business case to change the underlying structure - by definition there was a “good reason”.

In the situations the two of us have discussed, there is no business case to create these interfaces in the first place. Where is the good reason?

> Even so, you should still not send your internal representation that may change across the wire and do some type of mapping. Are you going to send the same model that came from your ORM that’s tied directly to your database across as the representation to the outside world?

What ORM? What database? If I'm using an ORM and a database, high-performance time operations are likely out of the question.