Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Faster CRDTs: An Adventure in Optimization

josephg.com

Post reply on HN
Print view View original

111–120 of 154 posts

Re: Faster CRDTs: An Adventure in Optimization

#111

Post by josephg »

hinkley wrote: post #75

I'm getting mixed messages on CRDTs. Are we at the point now where they are general enough that the human observer is not constantly confronted with 'surprises' from the behavior of the system? Some of the talks by Kleppmann go straight into the weeds and make it hard to tell if he's just nerding out about finer points or lamenting unsolved problems, or even paradoxes.

As a community, we’re in the process of crossing that river right now. A few years ago it was an accomplishment to get a text based CRDT working at all. Now implementations are starting to compete on features and performance, and they’re starting to see some use in real world applications. But there’s still some edge cases to iron out and understand in terms of memory size and pruning and things like that.

In a few years the rough edges will be ironed out and well understood, and there will be a good set of CRDT implementations you could use without worrying about this stuff. I think Yjs might already be there.

Re: Faster CRDTs: An Adventure in Optimization

#112

Post by maemre »

shrimpx wrote: post #103
zladuric wrote: post #91

Earlier quoted context omitted.

> especially target the first author because they have normally done the work As someone living with a recently promoted? (is that the correct term?) PhD in social sciences, this surprises me. Is that something specific for my country, for social sciences or my wife simply landed in a case full of rotten apples?

In computer science the first author does the work and is usually a PhD student. The last author is usually the professor that pushed and helped develop the idea, provided funding, and probably wrote or was heavily involved in writing the paper’s abstract, intro and conclusion sections — the bulk of “framing” the work. But there are exceptions. Some profs are less student-oriented or don’t like delegating so much, an…

In a lot of math disciplines, the papers follow the Hardy-Littlewood rule, so the author names are ordered alphabetically [1]. Maybe, that's what you've been noticing. In my area (programming languages, which may be sometimes theoretical but it's mostly a mixed bag), I noticed only one group follow that convention. Others follow the "first author is the main contributor, last author is the advisor" convention you described.

[1]: https://en.wikipedia.org/wiki/Academic_authorship#Authorship...

Re: Faster CRDTs: An Adventure in Optimization

#113

Post by josephg »

gfodor wrote: post #95
josephg wrote: post #2

Hello HN! Post author here. I’m happy to answer questions & fix typos once morning rolls around here in Australia

Thanks for ShareDB. It’s dope. I extended it to support collaborative voxel editing ( https://jel.app ) and works great.

Oh that’s cool!! Did you use json-ot for that? I haven’t touched that code in years and it’s delightful people are actively maintaining it and using it to make cool stuff.

Re: Faster CRDTs: An Adventure in Optimization

#114

Post by rtpg »

What was the original paper referenced in the article? I couldn’t find a link or title. I remember being in France and being with some researchers working in the CRDT space and am wondering if I might know the authors

Re: Faster CRDTs: An Adventure in Optimization

#115

Post by jhgb »

knuthsat wrote: post #40
makmanalp wrote: post #31

Earlier quoted context omitted.

> Problem is that academics are rarely experts at programming or have knowledge of computer architectures as much as someone in the industry. There are various tricks that are never taught at college, therefore academics have no idea some stuff even exists. I want to push back on this generalization a bit. The academics that are focused on pushing the mathematical boundaries of discrete optimization are focused, no s…

I must say that when it comes to discrete optimization, the genetic/ant/simulated annealing/etc. stuff is more popular in academia than in industry (at least the industry that doesn't heavily include academics). Works like Lin-Kernighan heuristic are extremely rare and a bunch of knowledge exists in industry only. Even the mentioned heuristic was for decades being implemented incorrectly until one individual came and…

> Even the mentioned heuristic was for decades being implemented incorrectly until one individual came and demonstrated its superiority (K. Helsgaun).

Does this mean that the Linkern program in the Concorde TSP suite is also implemented incorrectly?

Re: Faster CRDTs: An Adventure in Optimization

#116

Post by GormanFletcher »

> There's another approach to making CRDTs fast, which I haven't mentioned here at all and that is pruning.

Pruning is a key thing I appreciate about Yjs, because it's not just a performance optimization - it's a privacy feature. Users often expect that if they delete something from a document, it's gone unless they have explicitly turned on document revisioning. A CRDT without pruning leaves every accidental paste or poorly phrased remark in the permanent record.

Re: Faster CRDTs: An Adventure in Optimization

#117

Post by zadler »

_hl_ wrote: post #69
gritzko wrote: post #35

About a decade ago, I implemented the Causal Tree CRDT (aka RGA, Timestamped Insertion Tree) in regular expressions using a Unicode string as a storage. Later we made a collaborative editor for Yandex based on that code. It used many of the tricks as described in the text, even the optimization where you remember the last insertion point. So I am terribly glad it all gets rediscovered. The code is on GitHub [1] There…

I remember seeing that (regex CTs) and immediately thinking "wtf, why would anyone want to do that". Took me quite a while to understand that it's actually a pretty clever way to write fast state machines in browserland. So thank you for this work!

And let’s face it, anything is better than writing JavaScript.

Re: Faster CRDTs: An Adventure in Optimization

#118

Post by _delirium »

zladuric wrote: post #91
JW_00000 wrote: post #81

By the way, as someone who has published academic papers, if you're ever bothered about a paper or have some comments, don't hesitate to mail the authors. (Their e-mail addresses are always on the paper; especially target the first author because they have normally done the work.) We are happy to hear when someone has read our work and I at least would've liked to have known if someone found a problem with my papers.

> especially target the first author because they have normally done the work As someone living with a recently promoted? (is that the correct term?) PhD in social sciences, this surprises me. Is that something specific for my country, for social sciences or my wife simply landed in a case full of rotten apples?

It's definitely more normal in the social sciences for the senior author to be first, so your wife's experience is probably not strange for her field. What people assume about author order really varies a ton between fields.

Re: Faster CRDTs: An Adventure in Optimization

#119

Post by feikname »

meepmorp wrote: post #90
Diggsey wrote: post #30

Earlier quoted context omitted.

Yeah, I've also seen several academic papers on performance or "optimization" of existing algorithms which just demonstrate a complete lack of knowledge about how those algorithms are implemented in practice. For example, there was a paper explaining how you could optimize the GJK algorithm by reducing the number of distance checks required, and in turn the number of square-roots... Despite the fact that everyone (in…

> Despite the fact that everyone (including the authors of the original GJK algorithm) knows that you don't actually need to do a square-root to compare distances.. Academia's purpose is to produce research, typically measured in publications per unit time. Optimizing one paper leads to a global reduction in the size of the literature by pruning opportunities for subsequent research, harming the overall performance o…

how is less and more accurate (read: not done wrong) studies pruning opportunities for future research?

from my view, it becomes easier to make research.

less, more condensed literature is easier to cite and read, as it's "unified".

from there, many other researches can easily base the work off the paper for novel research.

less doesn't necessarily mean worse.

Post reply on HN