sujayakar

it seems like libraries can't use import maps though, right? the final binary can provide that flag, but is there a way for library dependencies to specify their own import maps? the spec [1] has support for scoping, but I didn't see a way to integrate that with the Deno loader.

[1] https://github.com/WICG/import-maps#scoping-examples

Note that this paper was first submitted to arXiv in May 2020. I haven't been able to find any previous discussion by an expert, though.

> Bit-reverse is unimplemented on x86 for some reason, but bswap64() is good enough.

You totally nerd-sniped me! I implemented a basic "reverse 128-bit SIMD register" routine with `packed_simd` in Rust. The ideas to process 4 bits a time:

    let lo_nibbles = input & u8x16::splat(0x0F);
    let hi_nibbles = input >> 4;

Then, we can use `pshufb` to implement a lookup table for reversing each vector of nibbles.

    let lut = u8x16::new(0b0000, 0b1000, 0b0100, 0b1100, 0b0010, 0b1010, 0b0110, 0b1110, 0b0001, 0b1001, 0b0101, 0b1101, 0b0011, 0b1011, 0b0111, 0b1111);
    let lo_reversed = lut.shuffle1_dyn(lo_nibbles);
    let hi_reversed = lut.shuffle1_dyn(hi_nibbles);

Now that each nibble is reversed, we can flip the lo and hi nibbles within a byte when reassembling our u8x16.

    let bytes_reversed = (lo_reversed << 4) | hi_reversed;

Then, we can shuffle the bytes to get the final order. We could use a different permutation for simulating reversing f64s in a f64x2, too.

    let rev_bytes = u8x16::new(15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0);
    return bytes_reversed.shuffle1_dyn(rev_bytes);

Looking at the disassembly, if we assumed our LUT and shuffle vectors are already in registers, the core shuffle should be pretty fast. (I haven't actually benchmarked this or run it through llvm-mca, though :-p)

    __ZN8arbolito7reverse17he044c5155cfe877bE:
    push    rbp
    mov     rbp, rsp
    movdqa  xmm1, xmmword ptr [rip + 557012]
    movdqa  xmm2, xmm0
    pand    xmm2, xmm1
    psrlw   xmm0, 4
    pand    xmm0, xmm1
    movdqa  xmm1, xmmword ptr [rip + 557003]
    movdqa  xmm3, xmm1
    pshufb  xmm3, xmm2
    pshufb  xmm1, xmm0
    psllw   xmm3, 4
    pand    xmm3, xmmword ptr [rip + 556992]
    por     xmm3, xmm1
    pshufb  xmm3, xmmword ptr [rip + 556995]
    movdqa  xmmword ptr [rdi], xmm3
    pop     rbp
    ret

And, this does a full bitstring reversal, not just reversing the bytes like `bswap64`, right?

> The key is that multiplying by an odd number (bottom-bit == 1) results in a fully invertible (aka: no information loss) operation.

This is neat! How do you choose odd numbers so the final generated numbers are high quality?

Very cool! Independent of the cool use of `aesenc` and `aesdec`, the features for skipping ahead in the random stream and forking a separate stream are awesome.

> My current home project is bump-allocator + semi-space garbage collection in SIMD for GPUs. As far as I can tell, both bump-allocation and semi-space garbage collection are easily SIMDified in an obvious manner. And since cudamalloc is fully synchronous, I wanted a more scalable, parallel solution to the GPU memory allocation problem.

This is a great idea. I wonder if we could speed up LuaJIT even more by SIMD accelerating the GC's mark and/or sweep phases...

If you're interested in more work in this area, a former coworker wrote a neat SPMD implementation of librsync [1]. And, if you haven't seen it, the talk on SwissTable [2] (Google's SIMD accelerated hash table) is excellent.

[1] https://github.com/dropbox/fast_rsync

[2] https://www.youtube.com/watch?v=ncHmEUmJZf4

I'm very interested in this space! I've been hacking on some open-source libraries around these ideas: rsdict [1], a SIMD-accelerated rank/select bitmap data structure, and arbolito [2], a SIMD-accelerated tiny trie.

For rsdict, the main idea is to use `pshufb` to implement querying a lookup table on a vector of integers and then use `psadbw` to horizontally sum the vector.

The arbolito code is a lot less fleshed out, but the main idea is to take a small trie and encode it into SIMD vectors. Laying out the nodes into a linear order, we'd have one vector that maintains a parent pointer (4 bits for 16 node trees in 128-bit vectors) and another vector with the incoming edge label.

Then, following the Teddy algorithm[3] (very similar to the Hillis/Stele state transition ideas too!), we can implement traversing the tree as a state machine, where each node in the trie has a bitmask, and the state transition is a parallel bitshift + shuffle of parent state to children states + bitwise AND. We can even reduce the circuit depth of this algorithm to `O(log depth)` by using successive squaring of the transition, like Hillis/Steele describe too.

I've put it on the backburner, but my main goal for arbolito would be to find a way to stitch together these "tiny tries" into a general purpose trie adaptively and get query performance competitive with a hashmap for integer keys. The ART paper[4] does similar stuff but without the SIMD tricks.

[1] https://github.com/sujayakar/rsdict

[2] https://github.com/sujayakar/arbolito

[3] https://github.com/jneem/teddy#teddy-1

[4] https://db.in.tum.de/~leis/papers/ART.pdf

are there any good composable programming abstractions for expressing progress in a system?

as an analogy, I really like RAII-based cancellation for futures in rust. dropping a future means the caller is no longer interested, and the sane behavior of cancelling all of the subfutures is the default. this seems simple at first, but dropping a single future may end up cancelling operations on other threads, freeing buffers, and so on, and the programmer profitably stumbles into the correct behavior.

so, it'd be nice for having a similarly composable abstraction for reporting progress in an asynchronous system. `Control.Monad.Progress`[1] just uses a float in [0, 1] to represent progress, and `NSProgress`[2] has a bit more going on but still requires the programmer to manually partition a parent task into its subtasks.

I'm not sure this is altogether possible, but I could imagine 1) a library for expressing the ground truth of where parts of a system are and then 2) a heuristic based layer above for turning snapshots of the system into time estimates and percentages working well.

[1] https://hackage.haskell.org/package/progress-reporting-1.0.0...

[2] https://developer.apple.com/documentation/foundation/progres...

For Question 1, you can turn division by a known constant into multiplications + bitshifts using a library like `libdivide`[1]. Then, we could use the regular rejection sampling algorithm mentioned in the annotated code [2].

I'd be curious how the naive rejection sampling algorithm's performance compares to Lemire's algorithm's when both are updated to use libdivide...

[1] https://libdivide.com/

[2] https://github.com/colmmacc/s2n/blob/7ad9240c8b9ade0cc3a403a...

if you can email me (my HN username @dropbox.com) the email address associated with your account once you've sent the bug, I can take a look!

we just use our regular CI infrastructure for running linux, macOS, and windows. we have infrastructure for managing VMs for our different supported platforms, setting up filesystems, and so on.

here's a talk from one of our engineers on our macOS CI infrastructure: https://blog.macstadium.com/blog/virtualizing-mac-infrastruc...

yeah, we don't merge file contents. it's really hard to do this well, since you'd need to implement something like operational transforms for every different file type, and the cost of getting wrong is really high, since we'd be corrupting users' files.

I can see us perhaps doing this in the future for more targeted file types where the "rebase" behavior is well-defined, though.

here's some of the greatest hits from memory:

1) when we upload a file, we first ask the server which blocks we need to upload. this allows us to deduplicate blocks with other files or previous revisions of files you have. I had written some code like...

  let blocks_needed: HashSet<BlockHash> = ...;
  let file_blocks: Vec<BlockHash> = ...;
  let to_upload: Vec<_> = file_blocks
    .into_iter()
    .filter(|b| blocks_needed.contains(b))   
    .enumerate();

  for (offset, block_hash) in to_upload {
    ...
  }

the bug here is that we're computing the offset into the file after filtering, so we'd be uploading incorrect contents to the server. we have protections elsewhere that would prevent file corruption, but finding this bug pre-commit with trinity was pretty awesome.

2) nontrivial interactions between different components in the system are hard to test manually and come for free with trinity. trinity will simulate cancelling file transfers, crashing the system, and even dropping the local databases (to simulate disk corruption). these are all hard enough to test in isolation, but knowing how to combine them is almost impossible. so, having "automated test generation" for these cases is really useful.

3) the "theory of trees" seems like it'd be pretty simple, but canopycheck has found some really interesting cases, especially around moves. when we started, we hadn't really thought about how to handle move cycles, concurrent moves that cross ancestor chains, ...

hey, can you file a bug from the app? it will collect a report that we can use to diagnose. there's a "Report Bug" option adjacent to "Preferences..."

hey all, author of the previous post (https://news.ycombinator.com/item?id=22595782) here, and I'm happy to answer any questions about the system! I think the author isaac is here too.

we still have to check every file on startup, since we use the `ReadDirectoryChangesW` call on windows, but it should be less expensive on nucleus. but, now that we've rolled out nucleus, we can start exploring going beyond sync engine classic feature parity, like using the USN journal on windows.

I think a lot of projects in Rust take a hybrid approach with async, where they have some ambient "runtime" (like tokio, for example) and allow forking off futures to its executor. this is similar to the `go` statement referenced in https://vorpus.org/blog/notes-on-structured-concurrency-or-g... for trio. but looking at the pieces that don't rely on this ambient executor should be pretty close to how we structure our async code.

in my understanding, the pure futures approach in rust goes even further than the nursery approach in trio, where there isn't even a "local" notion of forking off a task in the background. if a future wants to do an operation in the background, it's responsible for `join`ing on it itself or finding some other way to ensure it gets `poll`ed. this setup is a good fit for rust since the parent future maintains ownership over its child, and dropping the parent future immediately cancels the background tasks.

but, for what it's worth, I think there's lots of tradeoffs in this space, and we have yet to find really good patterns for structuring async code. so it's good to see so much experimentation.

and on lobste.rs too :)

https://lobste.rs/s/ob6a8z/rewriting_heart_our_sync_engine

yep! it was 100% critical to have the experts on sync engine classic involved with nucleus. we shared the oncall rotation of maintaining the old system among the entire rewriting team.

IIRC, we had a team of about six engineers working on the core system itself plus a few product teams building features on top. and yes, the team did get recognition for their work, which definitely helped when we decided to begin rewriting!

for mac it's FSEveents: https://developer.apple.com/documentation/coreservices/file_....

> As soon as I paid for the Plus Plan, I started having to wait several minutes for a file to upload. Even from one computer to the other with LAN Sync enabled. The day before that, my files would sync faster than I could hit refresh in the browser I was developing in.

that definitely seems like a bug, could you report it? click on the dropbox tray, click on the dropdown in the top right, and then click "Report Bug." this will collect some information about your client to help us debug.

sure! the rust team has done a fantastic job with the language design, and once a programmer gets over the initial learning curve, the ergonomics of "pair programming" with the compiler are really great. they've put a lot of work into error messages, and the language definitely steers the programmer towards writing correct, efficient code.

also, a lot of the standard library APIs are really well thought out, and it's great to then use the type system to build great internal APIs as well. the ability to design APIs to make correct use easy and incorrect use difficult feels like good "ergonomics" to me :)

yeah, I'm familiar with those tools, and other teams at dropbox have used TLA+ for verifying their protocols, but we haven't done it for our system yet. we've spent most of our time on testing working on better randomized testing, with the idea that covering more surface area there has higher ROI. but I can definitely see value there, especially once the protocol "settles down" and sees less change over time.

we actually extensively use structured concurrency patterns with futures in rust.

it's easy to have "nested" futures in rust, where one top-level future (our control thread) owns its subcomponents (like a protocol component, scheduler component, and so on), and the `poll` method for the top-level future then `poll`s all of its subcomponents. in this case we manually write our own `poll` implementations, but it's also easy to express these patterns with combinators like `FuturesUnordered`.

then, we have really good cancellation properties in our system. if we decide to cancel a file, we just drop its future, and we can be sure that all of the resources held by its "subtree" of futures will be released.

hey everyone, author here! happy to answer any questions about the post, our system, or our usage of rust :)

does Go's compiler emit SIMD instructions? it'd be cool to see the disassembly for the final, column order version since that loop would vectorize well. the same question goes for the speed-of-light benchmark -- there may be room to push even further there if it's doing a single multiply at a time.

> In fairness, I don't recall any literature on these (as is the norm for high-end database computer science).

Check out Navarro's book Compact Data Structures: A Practical Approach. It's a really great survey of the literature from a data structures perspective. It also spends a lot of time on compressing these structures, an alternate perspective to learning/prediction, as you mention.

The modes are the sequence of seven notes you're choosing from. If we're counting in half-steps (where 12 half-steps is an octave and gets you back to the same note), the different modes would look like...

                    1    2    3    4    5    6    7
  Lydian:          (R,   R+2, R+4, R+6, R+7, R+9, R+11)
  Ionian (Major):  (R,   R+2, R+4, R+5, R+7, R+9, R+11)
  Mixolydian:      (R,   R+2, R+4, R+5, R+7, R+9, R+10)
  Dorian:          (R,   R+2, R+3, R+5, R+7, R+9, R+10)
  Aeolian (Minor): (R,   R+2, R+3, R+5, R+7, R+8, R+10)
  Phrygian:        (R,   R+1, R+3, R+5, R+7, R+8, R+10)
  Locrian:         (R,   R+1, R+3, R+5, R+6, R+8, R+10)
  
  Melodic:         (R,   R+2, R+3, R+5, R+7, R+9, R+11)
  Harmonic:        (R,   R+2, R+3, R+5, R+7, R+8, R+11)    

Then, once you have your mode, you form chords by picking a starting note (from one to seven) and then stacking every other note from there. We're only building triads, so stop after stacking three notes. So, if we're in Ionian, the chords would be...

  I:   (R, R+4, R+7)
  ii:  (R+2, R+5, R+9)
  iii: (R+4, R+7, R+11)
  IV:  (R+5, R+9, R)
  V:   (R+7, R+11, R+2)
  vi:  (R+9, R, R+4)
  vii: (R+11, R+2, R+5)

Instead of playing the three notes simultaneously, the arpeggiator here is playing them one at a time in different orders and octaves.

Hope that helped!

Yeah, I think it's pretty interesting to compare Germany with Japan in that case. Japanese cultural memory and historiography intensely remembers the suffering of civilians from famine, firebombing, and nuclear weapons [1] (but rarely from the military itself [2]), but even suggesting that German civilians suffered unnecessarily from strategic bombing in Der Brand (2002) earned Jörg Friedrich, a German historian of Nazi war crimes, widespread censure.

[1] Grave of the Fireflies is a gorgeous, heartbreaking film. Highly recommended!

[2] See the discussion of Okinawa in http://apjjf.org/-Mark-Selden/3173/article.html

It's one of those moments in war where technology leaps ahead of international law. Additional Protocol I to the Geneva Conventions in 1977 outlawed the attack of "works or installations containing dangerous forces" to the civilian population [1]. You'd be very hard-pressed to argue it was illegal at the time. Whether it was immoral is, of course, up for debate!

[1] https://ihl-databases.icrc.org/ihl/WebART/470-750071?OpenDoc...

Try Leavitt's Modern Method for Guitar! I'm totally in the same boat, and forcing myself to "slow down" and play really simple songs well in standard notation has helped my confidence a ton. It's totally reasonable to self-study the book if you're already fluent playing the guitar.

That's so cool! Any fun stories or obscure algorithms that came up?