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.

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.