Swift benchmarks

I once a while check Swift benchmarks against other languages to see how the language is speeding.

Here is Swift vs Java

Why is Swift so awful in Regex and Binary Trees?

3 Likes

This site has been mentioned before. The tl;dr answer is that the Swift code is not written idiomatically. Specifically, for the binary tree benchmark, the Swift code reads like a translated Java program. It uses an object to represent the node, and Swift's allocator is not optimized for creation of hundreds or thousands of small objects. For one, they are always heap-allocated. The last time this was brought up, someone rewrote the program to use an enum, and it was markedly faster than the Java version.

20 Likes

I’m going to submit an enum version and see if they will accept it. They may not as the binary-tree benchmark they have is explicitly about GC performance.

Still, if using a value type for performance like this in Swift is idiomatic I think they should accept it.

4 Likes

It would be cool if someone pitched that solution on the benchmarks game forum to replace the current one. Someone willing to brave the, uh, cultural challenges of that particular message board.

Also worth noting that the instructions for that particular benchmark are a little odd, and especially problematic for Swift:

When possible, use default GC; otherwise use per node allocation or use a library memory pool.
...
Please don't implement your own custom "arena"

Swift is unusual in that it has a GC, but its use is discouraged in favor of alternatives like value types in many circumstances (sometimes by wrapping a class but mitigating the performance consequences with things like CoW). It's easy to reach for classes, especially when writing a tree type, but it's not the only way to do it. Being required to use it leaves us in a bind.

You may get pushback that doing something other than using a class (or indirect enum) in Swift as not idiomatic, but IMO the best, most idiomatic way to implement this benchmark in Swift is with a type that uses an array of enums that store the left and right nodes as indices into that array. That solution ought to be even faster than an indirect enum (though you might have to battle the bounds checking to get peak performance... but withUnsafeBufferPointer is still perfectly idiomatic Swift when needs must :slight_smile:). But it'd be hard to argue this isn't a storage arena, even if it's using the standard library to do it safely and neatly. It may be that as-defined, Swift will always be slower because the instructions require you to implement a poor and arguably non-idiomatic solution.

15 Likes

Aside: I’m a bit surprised to hear you characterize ARC as GC; I’ve always thought a memory manager must have some form of cycle detection to be called “garbage collection,” and most docs (including Swift’s official) describe ARC in contrast to GC, not as a form of GC. Is there a subtlety I’m missing here?

1 Like

Eh, I could go either way. Wikipedia's comment matches my ambivalence:

Tracing garbage collection is the most common type of garbage collection, so much so that "garbage collection" often refers to tracing garbage collection, rather than other methods such as reference counting.

2 Likes

OTOH I'm all in favor of arguing about word definitions as an attack vector against the problematic rules of this particular benchmark...

2 Likes

One could read that as describing implementation approaches to GC (tracing vs ref count + cycle detection) that give equivalent functionality … but agreed, the term does seem to be ambiguous, at least on Wikipedia. (That article is a jumble; it could use some serious editorial love.)

Anyway, good to know I’m not missing something crucial about Swift. Thanks.

I submit an enum version some time ago. They first reject it, than accept it and finally reject it.

On the topic of reference counting performance in Swift, not long ago I linked a paper on improving RC performance by taking account of calling threads: Improving reference counting performance

While that particular implementation of Swift RC may not be the acceptable for some reasons, the results are nonetheless impressive. Obviously, mentioned benchmark would benefit tremendously without any change to the code. But what's more important, real world code benefits should be nothing to sniff at as well.

It will be great to know if Core Team has some considerations in that regard.

1 Like

I know the GC part of Swift for reference types will be stripped for a better memory management model in the future.

I love enums and value type ofcourse are better to use for Swift. Recursive Data Structures built with Enums like Trees and LinkedLists are cool to have and stuff but to be frank, they have been not been useful for me one bit because our programming languages are built on imperative programming language semantics. Would be nice to see Recursion Language Semantics be a focus for Swift in the coming future. Kinda necessary for AI driven applications.

Hi @Loooop – if I'm looking at the right thread about your submission, I can see two reasons for the rejection.

One is that you describe indirect enums as a hack – this seems to suggest to the mod that this isn't an idiomatic solution and should be rejected. I think it's innacurate to describe recursive enums as a "hack because Swift doesn't natively support recursive structures." This is the explicit design of the language, not some interim workaround.

The other reason seems to be that the requirement is "to use the same node structure at depth 0 as at depth 1 and depth 2 and…". That's an unfortunate limitation, since it means you can't fully use Swift's enum capability, but I see where he's coming from in that you should have the same number of allocations to compare apples with apples (though, keeping the number of allocations the same isn't quite the same as requiring the same structure at all levels. It's still an improvement to use enums (and therefore more idiomatic, as well as being faster) because you can use pattern matching. I think this will fulfill the criteria better:

  indirect enum TreeNode {
    case node(TreeNode?, TreeNode?)
  
    func check() -> Int {
      switch self {
      case let .node(l?,r?):
        return l.check() + r.check() + 1
      default:
        return 1
      }
    }
  }
  
  func createTree(_ depth: Int) -> TreeNode {
    depth > 0
      ? .node(createTree(depth-1),
              createTree(depth-1))
      : .node(nil,nil)
  }

This still seems to be over 5x faster by my measurement. That's on Darwin though, someone with a Linux box should check that is the case on that platform too since the runtime for classes on non-Darwin platforms differ significantly. Also, worth double checking the memory allocation is twice the previously submitted candidate.

edit: alternatively you could stick with the leaf/node enum and adjust the depth numbers to match the desired allocation... that would match the desired solution in the real world, but sticking with a minor tweak to the current code probably is the easier path to an accepted improvement.

8 Likes

Just a quick run to my linux, I do see around 2-3x speed up (compared to the current website's code).

2 Likes

Hi Ben, I describe the struct version as a hack, not the enum one.
On my mac the enum version is five times faster, too.
But on Linux the enum version is only about two time faster.

P.s. the number of allocations is the same both if an optional is used as a flag for the terminal node and if a specific “.none” enum case is used otherwise. You can cheat with allocation number (and make the program way way faster) if you pass the same child as left and right child but I didn't.

P.p.s. They require the same data structure for all nodes. For me, whether you return treenode.childs(l,r) or treenode.none, you return the same data structure: an enum TreeNode data structure.

That was my thought as well here. I'll combine all of the various suggestions from this thread into my enum code and then submit it in the hopes of getting a discussion going.

I still assume it will be rejected as the benchmark is one specifically for GC, but I also think that for Swift the correct approach to the problem is to use an enum.

There are other benchmarks there that I might update as well that should be less contentious, but still offer room for improvement.

2 Likes

There are other benchmarks there that I might update

Here's an easy win: someone contributed Swift code for Mandelbrot but there seems to have been some misunderstanding — instead of source code for one program in one file, they contributed 3 or 4 versions of the program in one file.

It would be great if someone split them out, tested them, and contributed them - one program to one tracker issue.

https://salsa.debian.org/benchmarksgame-team/benchmarksgame/issues/264