Indirect enums vs classes

Development Compiler
1

Hi!

I'm new to the here and I'm currently doing a project in Swift for my compilers course. I was doing an implementation of a stack and a queue, since I had already done it in C++ in my third semester of uni. After chatting with Claude, I discovered indirect enums that let you point to another enum of the same type. At the end of the day, I implemented the Stack with indirect enums and the Queue with classes. Is there a difference in performance of using indirect enums over classes for the Stack?

2

Why not do both and measure the difference with a benchmark?

In practice you’ll encounter many such questions over your career - and there’ll be theoretical answers — but it is super useful to also validate with real numbers, sometimes theory and practice decides to go separate paths… (as the theory at times is non-complete and flawed)

5 Likes
3

Also, remember to test with release builds, not debug since the execution times are slower in debug builds.

4

Remembered that I did a comparison using indirect enums versus classes with binary search trees (BST). In this comparison, indirect enums were slower compared to classes.

Build for release: swift build -c release and first unzipping the test files in ../samples, then execute:

$ ./.build/release/bstree ../samples/Bulk.txt ../samples/ignore-words.txt 10

First, class based BST:

Listing 10 most common words.
Export took: 0.0018169879913330078
  1. ja.................. 62796
  2. to.................. 41099
  3. in.................. 32681
  4. he.................. 32108
  5. that................ 27021
  6. on.................. 24312
  7. his................. 20040
  8. it.................. 16443
  9. for................. 16186
 10. with................ 16070
Count of words: 2379836, count of unique words: 97144
 >>>> Time 1.947219967842102 secs.

Then the indirect enum based:

Book file: ../samples/Bulk.txt.
Stop words file: ../samples/ignore-words.txt.
Listing 10 most common words.
Export took: 0.0018529891967773438
  1. ja.................. 62796
  2. to.................. 41099
  3. in.................. 32681
  4. he.................. 32108
  5. that................ 27021
  6. on.................. 24312
  7. his................. 20040
  8. it.................. 16443
  9. for................. 16186
 10. with................ 16070
Count of words: 2379836, count of unique words: 97144
 >>>> Time 7.801893949508667 secs.

Here, indirect enums are clearly slower, ~8 secs compared to ~2 secs. This test was executed on my MacBook Neo.

Disclaimer: haven't analysed why the difference, it could be something in my code in how I use indirect enums. Maybe I'm holding them wrong.

Also, a different use case to yours, but you could do a similar comparison.

Code for this can be found at BooksAndWords/BSTree at main · anttijuu/BooksAndWords · GitHub

1 Like
5

There's a tangentially related use case of immutable recursive data structures, although it's more applicable for some static data instead of queues/stacks which are dynamic.

1 Like
6

If you care about performance, I'd investigate using Array (or maybe UniqueArray) for your stack. If you want to do a queue, you'll instead want a Deque, which you could get from swift-collections, or if you wanted you could implement it on top of an Array… a straightforward way to get a deque from an array is to have a base property that tells you where element 0 (of the deque) lives in the underlying Array. You can work out how to implement the various deque operations from there.

You might want to think about why it is that Array or Deque might be faster than constructing a stack from individual nodes. If you're using a Mac, investigating how much time various operations take using Instruments might give you some clues.

1 Like
7

An even simpler way, if you have slightly looser performance requirements, is this:

  • the queue consists of two arrays, in and out
  • to enqueue an element, add it at the end of in
  • to dequeue an element, check if out is non-empty, and pop the last element of out if so. Otherwise, reverse in and append its contents to out.

This has amortized O(1) enqueue and dequeue operations, but occasionally the dequeue will require O(n) steps. (But if you think about it, growable arrays are already like this anyway.)

2 Likes