rbehrends

No. It's more like what the following piece of code produces:

  def convert(xml):
      import re

      parsed = re.split(r"(<.+?>)", xml)
      output = parsed[0]
      tags_with_pos = []
      for i in range(1, len(parsed), 2):
          tags_with_pos.append((parsed[i], len(output)))
          output += parsed[i+1]
      return tags_with_pos, output

> Remember, the actual i4i patent at issue was filed in 1994, and it only matters if there was prior art from before 1994. It might have been novel at the time.

I am aware of the date of the "invention". I was programming on 8- and 16-bit computers in the 1980s and I was using this and similar kinds of formats for non-textual data, simply because it was easier to do this in assembler than writing a parser, paired with the difficulty of finding unused special bytes in binary data to separate meta-information from the data proper.

And I was also talking about non-obviousness, not novelty.

It's not about storing XML, it's (as far as I understand the patent) about a specific representation of XML that can be more efficient to read.

The patent is about representing documents with markup (XML or otherwise) not by embedding them in the text, but rather having them stripped and maintained as a separate list of (tag, position) pairs, with the document only containing the raw text.

I'm only surprised that Microsoft couldn't find prior art, because having a (content-type, address) index at the beginning of a file is not exactly an unusual representation. It also reminds me that the USPTO's idiosyncratic usage of non-obviousness doesn't really match my intuition.

> I never use three way string comparison, and so I wondered when other programmers use it.

Three-way comparisons show up naturally when doing a binary search or implementing binary trees.

Interestingly, the binary search implementation in the Go stdlib doesn't need it, but that's because it's only doing part of what you'd normally expect a binary search function to do and shifts the responsibility for the actual equality check to the caller [1].

[1] https://go.dev/src/sort/search.go

The actual waste here is that while the European Parliament normally meets in Brussels, it is still bound by a 1992 decision to have a monthly session in Strasbourg [1]. This creates a huge and unnecessary overhead (shuttling 705 MEPs back and forth, maintaining separate offices in Strasbourg and other unnecessary duplication of efforts), of which this additional flight is just a small part. This could be fixed by deciding that the European Parliament meets in Brussels year-round.

[1] https://en.wikipedia.org/wiki/Seat_of_the_European_Parliamen...

Its caching system is also smart enough to handle #include dependencies, so for simple C/C++ projects, it can also function as a make alternative (without having to write a Makefile).

Plus, it makes cross-compilation really easy.

> It depends on the runtime. In the case of Go e.g. the compiler inserts potential "yield"-s at every function call[1].

> And in the case of Swift the atomic "release" calls at ends of scopes will run regardless whether there are hot loops or not.

Yes, but Nim does neither. Nim does insert write barriers, but that's only if you (1) write pointers to heap-allocated memory and (2) don't use the mark-and-sweep GC, so that can't explain big performance differences for those benchmarks where you primarily iterate over arrays.

> Also, you pointed to 3 languages with 3 different memory management strategies and 3 different toolchains (Rust is LLVM-based; Nim compiles to C and then calls a C compiler, GCC recommended; D has its own non-GCC non-LLVM compiler). It feels weird to put them in the same bag implementation-wise.

You don't seem to be aware of it, but D actually has an LLVM-based compiler (LDC). Nim can also utilize LLVM via choosing clang as its backend. You can definitely use them to generate equivalent LLVM IR and compare that. There's nothing weird here, this allows us to rule out differences related to the backend.

A runtime isn't some sort of magic thing that inserts itself into hotspots. Several of these benchmarks are just looping over pointerfree arrays for almost all of their runtime and still show differences. Unless you call parts of the runtime, implicitly or explicitly, it shouldn't result in overhead.

Allocation-heavy or write-barrier-heavy code might make a difference, but you literally have performance differences while iterating over arrays of scalars. And even then, last I benchmarked it, Nim actually compared favorably with e.g. jemalloc.

No, not really.

Languages like Nim/Rust/D/etc. should not have significantly different speeds for equivalent implementations for these kinds of benchmarks, as they ultimately can be written to compile to equivalent LLVM IR and thus the same machine code.

What you're usually seeing when you see such large differences is that there are differences in the implementation of the algorithm or of a standard library function.

There's nothing about these kinds of languages that should result in inherently significant performance differences on such synthetic microbenchmarks.

This was kicked off by Lynn Conway's famous VLSI design course at MIT [1], which began the Mead & Conway revolution.

You can find a more detailed write-up of that course and other courses it inspired (as well as some of the practical challenges involved) in her retrospective in IEEE Solid-State Circuits Magazine [2].

An excerpt:

> "Importantly, these weren’t just any designs, for many pushed the envelope of system architecture. Jim Clark, for instance, prototyped the Geometry Engine and went on to launch Silicon Graphics Incorporated based on that work (see Fig. 16). Guy Steele, Gerry Sussman, Jack Holloway and Alan Bell created the follow-on ‘Scheme’ (a dialect of LISP) microprocessor, another stunning design."

[1] https://ai.eecs.umich.edu/people/conway/VLSI/MIT78/MIT78.htm...

[2] https://ieeexplore.ieee.org/document/6393023

And if you want something OSI-approved you can use either the MIT-0 [1] or the Zero-Clause BSD [2] license. The MIT-0 license is the MIT license without the attribution requirement, the Zero-Clause BSD license is (somewhat misleadingly) the ISC license without the attribution requirement.

[1] https://opensource.org/licenses/MIT-0

[2] https://opensource.org/licenses/0BSD

Fossil's intended use case is different from Git's; it was originally built as the VCS for SQLite. In terms of its target audience, it's basically GitHub-in-a-box for small or medium-sized teams. Implementation/usability-wise, it does some things better than Git, does other things worse, and yet others simply different (in a way that some may find better, some may find worse).

Thanks, but I do not plan to extend this project to other languages. I put it together a while ago as an illustration that conventional wisdom regarding GC cost is not what many people think.

If I were to expand it, I'd look at other allocation patterns rather than more languages; I've already good a fairly good cross-section of garbage collectors and malloc() implementations, so I don't really need any more.

This is not only a dated paper (a decade and a half old), but it relies on assumptions that do not necessarily hold in practice.

If you test actual allocation performance on actual current day hardware, you may end up with completely different results, e.g.:

https://github.com/rbehrends/btree-alloc

This can be easily illustrated using this example [1], which uses both the Boehm GC (v8.0.2) and jemalloc (v5.0.1), directly installed via Homebrew, as well as the system malloc on macOS to implement the binary trees benchmark from the benchmark game.

The benchmark keeps a large live set and allocates aggressively, making it an unattractive scenario for many GCs.

The Boehm GC is being run with the following four distinct configurations:

- Four marker threads in parallel, trading CPU time for wall clock time and lower pause times.

- Single-threaded marking.

- GC disabled, all memory is freed explicitly.

- Incremental collection (using virtual memory).

The results, run on a Macbook Pro with a six core 2.6 GHz Core i7:

  $ make benchmark DEPTH=21
  # jemalloc explicit malloc()/free()
  /usr/bin/time ./btree-jemalloc 21 >/dev/null
         17.53 real        17.40 user         0.11 sys
  # Boehm GC with four parallel marker threads
  GC_MARKERS=4 /usr/bin/time ./btree-gc 21 >/dev/null
          8.50 real        10.87 user         0.09 sys
  # Boehm GC with single-threaded marking
  GC_MARKERS=1 /usr/bin/time ./btree-gc 21 >/dev/null
         10.40 real        10.33 user         0.05 sys
  # Boehm GC with explicit deallocation
  GC_MARKERS=1 /usr/bin/time ./btree-gc-free 21 >/dev/null
         11.75 real        11.70 user         0.04 sys
  # Boehm GC with incremental collection (single-threaded)
  /usr/bin/time ./btree-gc-inc 21 >/dev/null
         18.39 real        16.40 user         5.11 sys
  # System malloc()/free()
  /usr/bin/time ./btree-sysmalloc 21 >/dev/null
         64.43 real        63.69 user         0.71 sys

Obviously, one should not read too much into this, as this is a very specific scenario with its own very specific allocation behavior that will not match other use cases. And one can speed up this specific example easily with a specialized allocator (as all allocations have the same size and predictable lifetime). Plus, different GCs make different tradeoffs, and so do general purpose manual allocators.

But for throughput at least, the worries about GC overhead tend to be exaggerated.

In practice, any language with proper value types will also spend only a fairly small fraction on allocation and garbage collection, so overhead becomes less of a problem.

[1] https://gist.github.com/rbehrends/528fc713c24195b1c8aefda074...

> The way you say "useful" brings to mind Inigo Montoya in Princess Bride: "you keep using that word. I do not think it means what you think it means."

Concurrency and parallelism has been what I've been working on for several decades. I have, inter alia, implemented concurrency mechanisms with strong safety guarantees for more than one language (among them two relying on shared memory [1, 2]), so yes, I think I have a pretty good idea what I'm talking about.

> I see accidental data races a lot more than any other kind of race condition;

And I didn't say otherwise. Freedom from data races (with the caveat that there are also benign data races that you sometimes want to exploit and that you want language mechanisms for) is more or less a necessary byproduct of most schemes to reason about concurrency; but on its own, its woefully inadequate for the reasons that I talked about.

> I'd guesstimate that avoiding them gets you 90+% of the way to thread safety.

If this were the case, then you'd practically never have any problem with thread safety in actor languages; that is not the case.

A simple and extremely common pattern where freedom from data races falls short is the following:

  if (obj->condition())

    obj->action();

If `obj` were just a monitor (i.e. an object that guarantees atomicity for individual operations), the code still wouldn't be thread-safe. What you generally want is thread safety at the transactional level, not at the level of individual operations. Any genuinely thread-safe language requires mechanisms that operate at the transactional level (though, obviously, not necessarily literal transactions in the DB sense), i.e. sequences of operations that you want to be atomic or non-atomic only in a controllable fashion. (Though, at the same time, it is also necessary that any such mechanism provides escape hatches for when it would impede concurrency [3].)

> Are there any practical / commonly used programming languages in which you can prove thread safety with that approach for significant programs?

First, I am not saying that being able to formally prove properties is a necessary element of concurrency (though there are systems that do exactly that, but that's beyond the scope of what I mentioned). But even when you're reasoning about program behavior informally, that relies on the same principles. Your code assumes some precondition and wants to arrive at a postcondition and you have to be sure that other threads don't muck up what your code is trying to accomplish.

The larger point is that with just the absence of data races, we still have a combinatorial explosion of ways that threads could interact with one another: most useful concurrency schemes (including Rust's) function by cutting down on that combinatorial explosion and limiting ways in which threads can interact with one another (and thus, possibly, in undesirable ways).

[1] https://link.springer.com/chapter/10.1007/11424529_17

[2] https://onlinelibrary.wiley.com/doi/full/10.1002/cpe.3746

[3] E.g. https://dl.acm.org/citation.cfm?doid=1297027.1297042; while the paper is about software transactional memory, the mechanism extends to critical regions in general.

Okay.

First, I was talking about useful definitions of thread safety. That was language-agnostic, not related to Rust. And if absence of data races were all that Rust guaranteed, then Rust indeed wouldn't be much of a help. What Rust actually does is require you to be (fairly) explicit about threads interacting with each other, which is a much stronger type of guarantee [1]. Rust comes with a default setting derived from the general shared-xor-mutable principle that threads don't mess with each other's data without permission, which makes it easier to reason about thread interaction.

Second, the OP was comparing Rust to actor languages. Actor languages also don't have data races and don't require mutexes (because the memory spaces of actors are disjoint and actors themselves are sequential). In fact, actor languages provide even stronger guarantees, as actors can only interact with each other at well-defined points. "Fearless concurrency" hails back to the 1970s. It is not a new invention, nor is it unique to Rust. It is great that Rust supports it, but I really wish people would stop talking about it being novel and unique.

[1] Which is not to say that Rust's choices don't come with tradeoffs, but then, in the area of concurrency, you cannot realistically avoid tradeoffs. In Rust's case, as with actors, the primary tradeoff is performance for safety.

What he is presumably talking about here is lexicographic DFS (as opposed to an unordered DFS), i.e. a DFS where the traversal order matters. To be precise: given a rooted digraph G with a set of vertices, an ordered adjacency list for each vertex, and two vertices a and b in G, does a DFS traversal of the graph that follows each adjacency list in order, visit a before b or b before a?

In practice, what we are interested in in particular is both a reproducible preorder and postorder ordering based on the DFS traversal, which is of use in other algorithms (such as Tarjan's algorithm for strongly connected components [1]).

This problem is P-complete and under the assumption that P != NC and under the parallelization assumptions underlying NC [3], is difficult to parallelize.

So far, this is not very controversial, but in practice, NC does not properly reflect what we think of as "inherently sequential"; especially the assumption of a polynomial number of processors is a bit odd when you're not dealing with hardware circuits.

On top of that, we often aren't interested in all possible graphs, but only specific types of graphs.

As a consequence, yes, lexicographic DFS can be parallelized for many use cases or in a fashion that we care about. As a simple example, lexicographic DFS for trees can be parallelized efficiently.

More generally, lexicographic DFS is already extremely fast if we have an existing in-memory representation of the graph (linear in the size of the representation with a small constant factor). It may take longer to construct the graph than to calculate a depth-first ordering of the vertices. In this case, we may not want to parallelize the DFS algorithm as such, but organize the construction of the graph so that we can run DFS in parallel with the construction.

This is of particular interest if we can't fit the graph in memory or if computing the edges of the graph is expensive. For example, we may not be able to parallelize the search as such, but we can instead parallelize the neighbor expansion.

The biggest issue here is that lexicographic DFS is a rather specialized problem in the family of graph search problems and many, many interesting types of graph searches can be parallelized just fine. For example, we can easily construct a parallel version of the A* algorithm; it will not explore the graph in the precisely same order, but as we are dealing with an algorithm guided by a heuristic, this is rarely a problem in practice.

[1] Though we have, contra ESR, parallel algorithms for strongly connected components in directed graphs that do not require a DFS ordering for the entire graph [2].

[2] See the previous work section of this thesis, for example: https://www.cs.vu.nl/~wanf/theses/matei.pdf

[3] https://en.wikipedia.org/wiki/NC_(complexity)#The_NC_hierarc...

Freedom from data races is far too weak a condition to be useful.

Consider the following example: you have a single global mutex, and every read/write to memory is bracketed by a lock/unlock of that mutex. The resulting code, while horribly inefficient, is technically free of data races, but that does not really give you anything interesting in terms of thread safety.

Any useful definition of thread safety requires that you can reason about program behavior in the presence of concurrency.

One such approach is the idea of interference-freedom introduced by Owicki and Gries [1]. Somewhat simplified, assuming that you have a thread A with precondition P and postcondition Q, i.e. the Hoare triple { P } A { Q }, a thread B does not interfere with thread A if the parallel execution of A and B, given the same precondition P we can still prove Q ({ P } A || B { Q }), for any interleaving of A and B.

Obviously, proving such a property is undecidable in the general case. In practice, we therefore limit ourselves to simpler models that are easier to reason about by constraining how threads can interact with one another (e.g. transactions, actor model), but even then, you can still end up with situations that are undecidable in the general case.

[1] https://dl.acm.org/citation.cfm?id=2697004

The headline uses a too literal translation of the German word "Kartellbehörde" [1], which can (literally) mean cartel office, but in this case refers to the federal competition regulator (the "Bundeskartellamt" [2], which has this name for historical reasons).

[1] https://www.linguee.de/deutsch-englisch/uebersetzung/Kartell...

[2] https://en.wikipedia.org/wiki/Federal_Cartel_Office

Well, one standard deviation is far more than just "a few IQ points". One general problem is that much of this stuff tends to be very US-centric. If you look at British data related to poverty [1] and the IQ of children [2], you get a somewhat different picture. You even have two different black populations with shared genetic ancestry, but different economic outcomes and different average IQ. (And Black Caribbeans weren't doing as well when they first arrived, but a few generations later, the gap seems to be closing.)

More importantly, as pointed out in an article by Kevin Mitchell [3], a professor of genetics and neuroscience in Dublin, we do not really know of any plausible mechanism by which such differences could have evolved. In the end, if you want to do science, you have to propose a theory by which an effect can be explained and then test that theory. What Murray & Co. have never done is to provide a testable theory that explains how cause and effect are supposed to be related.

[1] http://www.poverty.org.uk/low-income-and-ethnicity/

[2] http://www.unz.com/jthompson/intelligence-of-5-year-olds-in-... (not keen on citing James Thompson here, but I didn't find an open access source for the data)

[3] https://www.theguardian.com/science/blog/2018/may/02/why-gen...

Luckily, somebody already did the work [1].

In short: There is an implication in the Coleman essay that African Americans have less wealth because they spend more.

Problem with that:

1. While black people spend more on these items than white people, white people spend correspondingly more on other luxury goods.

2. Quote: "[...] once income is controlled, if anything, black families actually have a slightly higher savings rate than their white counterparts. [...] If anything, it appears that blacks generally live more frugal lives than whites; a study conducted by the Institute on Assets and Social Policy using the 2013 Survey of Consumer Finances found that, at comparable levels of income, whites spend 1.3 times more than blacks (Traub et al.)"

So, yeah, the entire argument depends on a cherry-picked metric (we're leaving aside the question to what extent cars and clothing are necessarily Veblen goods and to what extent differences in types of spending are the result of different social constraints and incentives [2]) that does not reflect actual spending and saving habits well.

What Quillette essentially is: a Gish Gallop [3] in webzine form. Debunking all this takes time and effort and few people have the spare time to keep up with their output, and even then the debunking is often not seen by the original readers.

[1] https://boards.straightdope.com/sdmb/showpost.php?p=21121635...

[2] For example, the problem that it can be more important for a black person to appear well-dressed to compensate for racial bias than for a white person.

[3] https://en.wikipedia.org/wiki/Gish_gallop

> It also only refers to ownership, not borrowing, and both are equally important.

I addressed borrowing above. Borrowing is proving lifetime subset properties and that you therefore can avoid increasing the virtual reference count.

And this is not about whether this is useful for beginners. It is to illustrate inherent limitations of the approach.

I am talking about just using basic references & borrowing. Once you introduce reference counting (Rc<T> and Arc<T>) and copying, you open up a lot more options, of course, but at this point you also can't make any lifetime guarantees anymore, because objects can escape the "owner's" scope at will.

> This is a thing people say, but I think it's misleading. Reference counting can increase the lifetime of an object, but borrowing cannot. I've seen this really trip up beginners.

"With a maximum reference count of 1." As the reference count becomes 1 upon object creation, it cannot really be increased further. Hence, only operations that keep the (virtual) reference count at 1 or reduce it to 0 are allowed.

My point here is that you inherently cannot do things where you cannot prove that this virtual reference count can be capped at 1.

> Oddly, Rust's ownership system really does solve these problems

No. Rust's ownership problem solves it for trivial cases, at the cost of making it hard to do other things (such as sharing references past the lifetime of the owner without resorting to Rc<T> or Arc<T>, at which point you don't really have lifetime guarantees anymore).

The essential limitation of Rust is that (without resorting to Rc<T> and Arc<T>, which would put you back to square one) it is conceptually limited to the equivalent of reference counting with a maximum reference count of 1. In order to make this work, Rust needs move semantics and the ability to prove that an alias has a lifetime that is a subset of the lifetime of the original object) and may even sometimes have to copy objects, because it can never actually increase the (purely fictitious) reference count after object creation.

This inherent limitation makes a lot of things hard (or at least hard to do without copying or explicit reference counting). Structural sharing in general, hash consing, persistent data structures, global and shared caches, cyclic data structures, and so forth.

In short, you have the problem with shared references less, because Rust makes it hard to share data in the first place, for better or worse. (Again, unless you resort to reference counting, and then you get the issue back in full force.)

It is not a design error. You are making the mistake of equating reachability of a reference with making it legal to access it. And the problem is that the two often aren't one and the same.

As a simple example, you may still want to access a resource after it has been released. Closing a network connection, for example, does not mean that accessing it is invalid. The connection may still have state (such as statistics collected or whether a non-blocking close was clean) that is perfectly legal to access after release (and in fact may only be consistent/observable afterwards).

The Eiffel FILE class [1], for example, allows you to call `is_closed` at any time (as well as the various `is_open` functions). This is necessary because `not is_closed` is evaluated as a precondition for many other operations.

A more complex example is a resource that is shared by many threads. Whether that resource is valid is often not a question of whether a reference is reachable, but a function of complex distributed state. Sometimes this can be solved by atomic reference counting, but even then atomic reference counting is expensive.

[1] https://archive.eiffel.com/products/base/classes/kernel/file...

You can also have the exact opposite problem with RAII, where a resource survives the end of a transaction, because there is still a live reference to it hidden away somewhere (say, due to some debugging code holding on to it).

This is a classical liveness vs. safety dualism. "Something good will eventually happen" and "nothing bad will ever happen" are promises whose solutions are often in conflict with one another.

The general problem — to make transactional state changes and transactional control flow (i.e. expectations about these state changes) match up precisely — is not easy to solve in the general case, especially once you move on to things that are less trivial than simple resource acquisition/release matching.

Well, but this subthread was originally about Article 11. I'm not sure how you are getting from that to Article 13?

That's completely unrelated to ancillary copyright (the Article 11 stuff), however. That's the DMCA. You still have the right to quote, but Youtube is not required to host your content for pretty much whatever reason they like, including just taking whatever causes the least trouble for them in case of a DMCA takedown notice.

Your right to quote exists vis-à-vis the copyright holder, not third parties. A frivolous DMCA notice may hypothetically get the copyright holder in hot water, but does not affect your contractual relationship with Youtube. And Youtube does not have to defend your rights for you, they just have to comply with the notification, takedown, and counter-notification requirements.