Random idea: If you have a known sentinel value for empty could you avoid the reader needing to read the writer's index? Just try to read, if it is empty the queue is empty, otherwise take the item and put an empty value there. Similarly for writing you can check the value, if it isn't empty the queue is full.
It seems that in this case as you get contention the faster end will slow down (as it is consuming what the other end just read) and this will naturally create a small buffer and run at good speeds.
The hard part is probably that sentinel and ensuring that it can be set/cleared atomically. On Rust you can do `Option<T>` to get a sentinel for any type (and it very often doesn't take any space) but I don't think there is an API to atomically set/clear that flag. (Technically I think this is always possible because the sentinel that Option picks will always be small even if the T is very large, but I don't think there is an API for this.)
Yeah, or you could put a generation number in each slot adjacent to T and a read will only be valid if the slot's generation number == the last one observed + 1, for example. But ultimately the reader and writer still need to coordinate here, so we're just shifting the coordination cache line from the writer's index to the slot.
I think the key difference is that they only need to coordinate when the reader and writer are close together. If that slows one end down they naturally spread apart. So you don't lose throughput, only a little latency in the contested case.
That's a good point. They are very similar. I guess the sentinel design in theory doesn't need to synchronize at all as long as there is a decent buffer between them. But the cached design synchronizes less commonly the more space there is which sounds like it would be very similar in practice. The sentinel design might also have a few thrashing issues when the reader and writer are on the same page which would probably be a bit less of an issue with the cached index design.
Programming in assembly isn't really "hard" it mostly takes lots of discipline. Consistency and patterns are key. The language also provides very little implicit documentation, so always document which arguments are passed how and where, what registers are caller and callee saved. Of course it is also very tedious.
Now writing very optimized assembly is very hard. Because you need to break your consistency and conventions to squeeze out all the possible performance. The larger "kernel" you optimize the more pattern breaking code you need to keep in your head at a time.
This makes sense and it's really that last step. It's one thing to do pattern matching or bit flipping routines. It's a whole different ballgame to build a game engine. Maybe if I knew gamedev better I wouldn't be as intimidated by it, but it really does seem like a herculean task.
I think it'd be cool to do assembler on a Pi Pico or something, that seems like it would be a fun exercise.
But it is about code syntax. Languages like Haskell make it part of the language by only supporting single-argument functions. So currying is the default behaviour for programmers.
I think you are focusing on the theoretical aspect of partial application and missing the actual argument of the article which having it be the default, implicit way of defining and calling functions isn't a good programming interface.
It's still not very useful to hide the length. If you don't know the length and just start guessing with passwords of length 0 it only adds about 1/N extra guesses where N is the alphabet size compared to guessing strictly the right length. So it is a very small savings to know the password length.
It might matter a bit more for dictionary-based attacks (you don't have to bother hashing dictionary permutations that don't match the expected length) but I still suspect it doesn't save you much.
For opportunistic attacks, this could help you identify those with short passwords and only attack them. This is a factor of N speedup where N is the pool of people you are interested in attacking.
I think the more important aspect is that people will have 24h to slow down, think, and realize that they are being scammed. Urgency and pressure is one of the top tactics used by scammers.
Scammers will definitely call back the next day to continue. But it is quite possible that by then the victim has realized, or talked to someone who helped them realize that they are being scammed.
There's been some reporting recently where I live about a case of some woman being scammed.
She went to a bank to transfer the scammer money. They told her no. She came back the next day. The police got involved and explained everything to her. Then she came back the next day. After that, she apparently found another location which let her transfer the money.
There's basically zero chance a 24 hour (or any amount of a) cool off period will help these people.
It's not one example. The scammers purposefully target people like these. That's their business.
Like, I'm sure there's a small amount of people who normally wouldn't get scammed but fall for it in a panic. But, is that really such a big concern for Google that they absolutely must continue stripping user freedoms from us? Is the current 30s popup which needs 3 confirmations not enough? Will the new one really work?
> helping some people is great even if it doesn't help everyone
It's kind of funny, but I very much agree with this. It's just in this case, it's hurting everyone (in ways most don't even realize) so that you can help a few people.
It's like putting everyone in prison, because some people might commit a crime and this would save some victims. A bit of an overreaction, no?
Regardless one of the conditions surely is giving them permissions to sell this to starlink as and everyone else. So whether the information is the same is probably irrelevant, how they are using it is.
Probably, because you are now associating your internet browsing with your personal information. (I don't know if they have the sophistication to actually do this, but it is very possible.)
I actually disagree with Rule 3! While numbers are usually small being fast on small cases generally isn't as important as performing acceptably on large cases. So I prefer to take the better big-O so that it doesn't slow down unacceptably on real-world edge-case stresses. (The type of workloads that the devs often don't experience but your big customers will.)
Of course there is a balance to this, the engineering time to implement both options is an important consideration. But given both algorithms are relatively easy to implement I will default to the one that is faster at large sizes even if it is slower at common sizes. I do suspect that there is an implicit assumption that "fancy" algorithms take longer and are harder to implement. But in many cases both algorithms are in the standard library and just need to be selected. If this post focused on "fancy" in terms of actual time to implement rather than speed for common sizes I would be more inclined to agree with it.
I think it's important to think about architectural and domain bounds on problems and check if the big-O-optimal algorithm ever comes out on top. I remember Bjarne Stroustrup did a lecture where he compared a reasonably-implemented big-O-optimal algorithm on linked lists to a less optimal algorithm using arrays, and he used his laptop to test at what data size the big-O-optimal algorithm started to beat the less optimal algorithm. What he found was that the less optimal algorithm beat the big-O-optimal algorithm for every dataset he could process on the laptop. In that case, architectural bounds meant that the big-O-optimal algorithm was strictly worse. That was an extreme case, but it shows the value of testing.
Domain bounds can be dangerous to rely on, but not always. For example, the number of U.S. states is unlikely to change significantly in the lifetime of your codebase.
Rule 3 was true 1989, back then computers were so slow and had barely any ram so most things you did only was reasonable for small number of inputs. Today we almost always have large amounts of inputs so its different.
Rule 3 is still very much real. Fancy fast algorithms often have other trade-offs. The best algorithm for the job is the one that meets all requirements well... Big-O is one aspect, data is another, determinism of the underlying things that are needed (dynamic memory allocation, etc) can be another.
It is important to remember that the art of sw engineering (like all engineering) lives in a balance between all these different requirements; not just in OPTIMIZE BIG-O.
Sure but the default (and usually correct) assumption when working at google (as an example) is basically "all numbers are big", so you you have to cluey about algorithms and data structures and not default to brute forcing something.
At 99% of shops it should be the other way around .
Even when you are working with large numbers, most numbers are usually small. Most of the code is probably not dealing with the large things, and a large thing may consist of a large number of instances that are individually small.
I've personally found it useful to always have concrete numbers in mind. An algorithm or data structure designed for N will probably be fine for N/10 and 10N, but it will often be inefficient for N/1000 or 1000N.
That's not quite true. Only one pixel is being activated at a time but the phosphors continue to emit light for many pixels. In practice you get a handful of lines lit to varying degrees at at time. Maybe 1-2 lines quite brightly lit and then a trail of lines that are fading pretty significantly (but still emitting light). They yes, our persistence of vision fills in the rest to provide the appearance of a fully lit screen.
The scale on the left was also very stuttery. Even when scrolling slow I could see the distance at the bottom updating at a very high frame rate and the scale on the left only moved occasionally which felt awful.
I find it hard to be too upset, better late than never. Would it have been better to upstream shortly after they wrote the code? Yes. Would it have been better if they also made a sizable contribution to fmmpeg? Yes. But at the end of the day they did contribute back valuable code and that is worth celebrating even if it was done purely because of the benefit to them. Let's hope that this is a small step and they do even more in the future.
As I said, the contribution is good, it's the communication via this blog post that I don't entirely like. It could have been different. It could have acknowledged better ways of engaging with ffmpeg (that would've benefitted both Meta and ffmpeg/the community, not _just_ ffmpeg).
But corporate blog posts often go this way. I'm not mad at them or anything. Just a mild dislike ;)
Yeah, I see what you mean. It basically shows that they contributed to ffmpeg purely because it helped them, but then they wrote this post to get good will for that contribution.
It seems that in this case as you get contention the faster end will slow down (as it is consuming what the other end just read) and this will naturally create a small buffer and run at good speeds.
The hard part is probably that sentinel and ensuring that it can be set/cleared atomically. On Rust you can do `Option<T>` to get a sentinel for any type (and it very often doesn't take any space) but I don't think there is an API to atomically set/clear that flag. (Technically I think this is always possible because the sentinel that Option picks will always be small even if the T is very large, but I don't think there is an API for this.)
reply