xoranth

The latest version can [^1], though anecdotally I've seen clang/LLVM being smarter about it.

[^1]: https://c.godbolt.org/z/vP8edfen7

> So you have to follow a comparison operation with either a conditional branch or a conditional move (and earlier processors in the x86 family didn't have conditional moves).

The x86 family has the `setCC` instructions [^1] that move bits from the flag register to a general purpose one. Example from godbolt, see `setg`:

https://c.godbolt.org/z/MY37oP9vz

[^1]: https://www.felixcloutier.com/x86/setcc

Yeah, makes sense. That said, (G)GP asked what could be done in raw assembly but not with C + intrinsics.

My point is that conditional moves are one of usecases badly supported by compilers, and that (may) require dropping to assembly.

More prosaically, getting compilers to generate branchless code reliably is difficult, there's no intrinsic for CMOV* and similars, and the builtins that should act as an hint don't work[1].

[1]: https://c.godbolt.org/z/6EWzKe5zd

Hindenburg doesn't short in order to drive down the price.

Hindenburg compiles and releases information they believe to be truthful about a company, which they shorted beforehand in order to profit from the information.

What I am talking about is sending orders only to cause a certain reaction (e.g. by convincing momentum traders that there is momentum in a certain direction).

If you mean shorting Masimo purely to drive down the price, that's market manipulation and is definitely illegal. E.g.

https://www.investor.gov/introduction-investing/investing-ba...

Thank you!

Amazing, thank you!

PS: where/what can I follow to know when it is published? Could you share your colleague github handle (I guess he'll have one :) )?

Do you have any paper/talk that gives more details about the "geometric XOR filter"? If not, is there any plan to publish something?

It's supposed to be a single expression. You can write multiple lines by encasing the expression with parentheses.

Hint: it says "committed my password", as in a "git commit" :)

It's not (just) the variety of topics, it is that HN has way more users (and therefore way more submissions).

A submission on lobste.rs will stay on top of recent/newest for days, on HN it might be minutes.

It is slower since it actually calls `memcpy`, instead of doing a single load. E.g.

https://godbolt.org/z/5xa33qbar

> I fail to see how that is better. Null-terminated strings are a terrible idea in the first place.

TLDR: you get extra bytes in your small strings

Long version: Copying from FBString code:

    struct MediumLarge {
     Char* data_;
     size_t size_;
     size_t capacity_;
    };
    // sizeof(MediumLarge) == 24

    struct FBString {
        union {
            // For accessing the last byte.
         uint8_t bytes_[sizeof(MediumLarge)]; 
         Char small_[sizeof(MediumLarge) / sizeof(Char)];
         MediumLarge ml_;
        };
    };
    

Then `bytes_[23]` is set to `24 - size of small string` for a small string. You also "steal" a couple of bits from `capacity_` as a tag to see if a string is small or large.

This has two advantages:

- You get to reuse seven of the eight bytes of `capacity_` in your small string (i.e. your max small string size is 23, not 16 as it would be with a simpler scheme). - You get a null terminator "for free" (though, of course, you still have size and capacity). This is on top of size/capacity.

This could be reduced to 16 bytes by making `size_` and `capacity_` uint32_t instead of size_t.

An even better representation is the one from `folly::FBString`.

There, the tag that indicates small string mode is not a particular bound on capacity, but the last byte of the struct that is set to zero. That way, the tag also acts as a null terminator for the stored string.

I think he meant this:

https://github.com/hanatos/vkdt

A ring buffer of pointers to structs is friendly to gather instructions. That said, the documentation shows a graph of operations applied to each packet. I'd expect that to lead to a lot of "divergence", and therefore being non-SIMD friendly.

(also, x86-64 CPUs with good gather instructions are rare, and sibling comments show that this is aimed at lower end CPUs. That makes SIMD even less relevant.)

> For example, in a typical event driven architecture where you have worker threads running each on separate core, there would be something to decide where the task is queued and usually the logic will take into account how busy particular worker thread is.

Wouldn't that work well only if the time taken by each task is predictable? I.e. you mention working on a trading system. But in a trading system you want to run the same branchless code path regardless of the kind of incoming event and whether you are sending an order or not after running the trading logic. So the individual "task" is very predictable.

On the other hand think of a task like "return all the comments for a certain page". The time taken by an individual task is unpredictable, proportional to the number of comments. So you'll regularly get one core getting enqueued a bunch of tasks with no comments, finishing quickly and then staying idle.

With work stealing, after finishing, that core would get a chance at "stealing" tasks from other threads' queues.

(of course, the architecture I am describing would be awful for a trading system)

> The operating system does nothing in this case, what it sees is a number of threads each running on its separate core that don't need to be preempted (hopefully).

Btw, I agree that pinning OS threads to each core and then layering something of your own on top of it is going to be faster. It is just that you can layer on top a green thread system (like Go), and get something thread-for-request -like.

> You are essentially asking the operating system to do the scheduling for you. But the OS will never be able to do it perfectly as it has no knowledge of what your application is doing.

From LMAX presentations, it looks like they want you to split your application into tasks [1], define a graph of task dependencies, have each core process a particular kind of task and have task processors communicate their producers via a ring buffer.

In particular, the allocation of tasks is static. The use of a ring buffer means that there is very little contention, and task processing is very efficient, but some cores might end up underutilized.

On the other hand, if you have a thread per request, and allow them to migrate between cores, idle cores can steal tasks from busy ones. So in theory you could get better utilization, but task processing is less efficient since you need to share more data between cores.

("threads" don't need to be OS threads, they can be green threads)

That said, I am not sure if GP meant this by thread-per-request, or "legacy" applications that use a thread pool, or something else.

[1]: https://www.slideshare.net/trishagee/introduction-to-the-dis...

In general, what are the advantage of a thread-per-request model? Better load balancing between cores?

> Hash table lookup is absolutely bounded by a constant, but going from L1 to L2 to L3 to RAM with anywhere between 0 and 5 TLB misses is far from constant.

Wait, don't the inner nodes of the page table contain the _physical_ addresses of its child nodes? Wouldn't that make it a most one TLB miss per hash table lookup (assuming key and value are adjacent in the hash table bucket)?

With the sorting solution, you can stream the result directly to a file _without_ holding the entire file in memory. So it can be better if you are memory constrained (e.g. if the files are bigger than what you can hold in memory), or if you want to hold the working set inside the CPU L3 cache as 'cperciva is alluding to.

Given that the depth of the page table tree is fixed at 3/4/5 depending on the architecture and kernel, I think most people would be confused if asked whether the average complexity of a hash table lookup is always really O(1).

Even senior developers that understand the TLB would likely think of it as "O(1), but with a big constant factor".

On a side note, one thing that the article doesn't mention is the possibility of using a Bloom filter. It trades an extra scan of a file for smaller hash tables/smaller set to sort with external sort.

You can generalize to

> Now, given two N log files we want to generate a list of ‘loyal customers’ that meet the criteria of: (a) they came on ALL days, and (b) they visited at least L unique pages.

while keeping linear time complexity and

  O(num records in first file * L)

memory complexity. It is not too different from the solution given in the article (just use 3 maps instead of two).

That means that multiple files doesn't need out-of-core if the maps for one file at a time fit memory.

Thank you!

> ...until they are slower, because GPU's latency hiding mechanism (with occupancy) hides load latencies very well, while CPU just stalls the pipeline on every cache miss for ungodly amounts of time...

Is the GPU latency hiding mechanism equivalent to SMT/Hyperthreading, but with more threads per physical core? Or is there more machinery?

Also, how akin GPUs "stream multiprocessors"/cores are to CPUs ones at the microarchitectural level? Are they out-of-order? Do they do register renaming?

So, in NVIDIA parlance, my Skylake laptop would have 128 "cuda cores"?

128 = 4 (physical cores) * 2 (hyperthreading) * 8 (AVX2 f32 lanes) * 2 (floating point ports per core)

US exchanges tend to either bust or price-adjust clearly erroneous trades retroactively.

That is good for unsophisticated customers, but it creates a disincentive for market makers to provide liquidity when there is a fat finger event. That in turn leads to larger price dislocations on such events.

(The reason is that the market maker faces adverse selection. Providing liquidity is a bet from the market maker that the price dislocation will revert. Price adjustment reduces the profit the market maker makes from mean reversion. But if the price dislocation was caused by a real news, the market maker will eat the full losses.)

Do you have any example of particle systems without fluid sim? (e.g. videos on youtube from old games, or names of old games that used them?)

That's likely the fastest way to do that without vectorization. But you'd need to upcast 's' to an uint64 (or at least an uint32). That means that vectorization would operate on 32/64 bit lanes.

With vectorization, I think the way to go is to have two nested loops, an outer advances by 32 * 255 elements at a time, and an inner one that loads 32 bytes, compares each character to 's', and accumulates on 8 bit lanes.

Then in the outer loop you do an horizontal sum of the 8 bit accumulators.

(Sorry, I was wrong. See here for the author's reply:

https://news.ycombinator.com/item?id=36627385 )