Tagged pointers

Does Swift use Tagged pointers to accelerate operations on simple objects like Int and short Strings?
I assume this would be constrained by the whole pointer signing thing which exists on Apple platforms.
I wonder if tagged pointers would be implemented differently in Swift on non-Apple platforms.
If you don't know what a tagged pointer is, read here: mikeash.com: Friday Q&A 2012-07-27: Let's Build Tagged Pointers

1 Like

Int doesn't require tagged pointer because it's a one-word value that doesn't require an allocation at all. String has a custom improved version of the tagged pointer optimization* called SmallString that's somewhat more efficient and supports up to 15 bytes of UTF8 rather than 11 bytes of ASCII subset.

*specifically it uses a two-word stack value, which is something that you can't do with object pointers but can do in Swift

3 Likes

Looking at the asm output of a simple program that uses an Int, it does appear that the Int is not an allocated object in the heap but is just a scalar like int in C. So that is encouraging.

But I have to say the asm output is a real mess, with repeated operations, unnecessary moves, etc.

If you compile this with "swiftc foo.swift -S" you will see what I mean:

private class Foo {

	var i : Int = 5

	init () {
		i *= 2
	}

	func foo () {
		i *= 23
	}
}

Make sure you are compiling with optimizations, i.e. -O or -Osize.

With -O there is still a lot of redundancy e.g. the multiplication by 23 happens twice (mul followed by smulh). The smulh is to get the upper 64 bits of the 128 bit result. Not sure why that's done. The Int value is in a register, which is good. Even though the core operation (multiplication) is done, the method still needs to call two other methods; one seems to be fetched from a vtable, the other is maybe the sp. It would be nice to someday see an annotated asm listing.

Not sure what this comparison is for:

        mul     x9, x8, x10
        smulh   x8, x8, x10
        cmp     x8, x9, asr #63
        bne ... (to a brk)

So it shifts the lower 64 bits of the multiplication result (x9) right 63 bits, which will usually give all 0's or all 1's, but compares that to the upper 64 bit of the multiplication result, which will not be the same usually.

I’m not an asm expert, but I would guess it’s checking for overflow. For the call, it might be checking for exclusive access. Using godbolt might help illuminate what’s going on.

As @Ben_Cohen put it in a WWDC20 talk,

Swift's use of value types actually makes tagged pointers less important, because values no longer need to be exactly pointer sized.

For example, a Swift UUID type can be two words and held inline instead of allocating a separate object because it doesn't fit inside a pointer.

Int and String are not class types, so they aren’t confined to using pointers. This allows Int values and small Strings to avoid storing their contents on the heap without using a tagged pointer. (For more information on how String works, here’s a blog post.)

Swift does use tagged pointers for compatibility with Objective-C (i.e. for NSNumber, NSDate, UIColor and NSIndexSet), but it doesn’t define its own tagged pointers AFAIK.

Part of the problem is that you’re compiling your code unoptimized. You should see a small improvement if you compile it with optimizations.

However, even with optimizations, there’s still some cruft in order to make the class compatible with the Objective-C class system. You can remove this cruft by using a struct instead of a class.

private struct Foo {
    var i = 5
    init() { i *= 2 }
    mutating func foo() { i *= 23 }
}

This allows the compiler to optimize your code further, since the complexity of using a class is removed. You can also use the overflow multiplication assignment operator (&*=) to avoid overflow checking.

If you haven’t already, I’d recommend watching the Protocol-Oriented Programming talk from WWDC15. It explains why you should prefer struct types over class types and how to replace classes in your program with structs and protocols.

Here are a few resources on how Swift works internally and how to optimize Swift:

6 Likes

On my machine, swiftc deletes foo entirely, and even if I add a call to it to avoid that, it inlines it. If I force-uninline it, I get this code for x86_64, which looks correct to me, aside from the annoying unnecessary stack frame.

	pushq	%rbp
	movq	%rsp, %rbp
	imulq	$23, 16(%r13), %rax
	jo	LBB2_2
	movq	%rax, 16(%r13)
	popq	%rbp
	retq

I'm less familiar with ARM, but I would assume, given this x86 codegen, that the comparison you're wondering about is related to overflow checking. If you change the i *= 23 to i = i &* 23 you should avoid that if so.

2 Likes

Yes I recall once trying to watch that, but the speaker begins making some strangely ageist comments in the course of using a Straw Man argument about older people. He comes off as being kind of a bad person. In general I don't take people who use Straw Man arguments seriously, nor people who are ageist.

Anyway, I'm not sure the embracing protocol oriented programming just because Swift is slowed down by its compatibility with Obj-C is a good enough justification. OOP still has its uses.

Yes I see that exists but shouldn't the overflow-checking version be the exception rather than the rule? Overflows are such rare events and while they are important, programmers do need to know about bits and bytes enough to know when an overflow is likely. If they don't know bits from bytes, they should use floating point.

No, most code is not performance-limited by arithmetic operations (more typically we see IO, memory, allocations, refcounting, dynamic dispatch, or various syscalls), and predicting where security vulnerabilities will come from is extremely difficult. "Safe, with the option for fast" is a reasonable choice.

5 Likes

It was a mess even after I used -O to optimize it.

But converting from class to a struct and using &%= did improve the code.

Terms of Service

Privacy Policy

Cookie Policy