[SR-3225] Hashable protocol causes huge memory consumption

[swift-ci]

Previous ID	SR-3225
Radar	None
Original Reporter	mattijah (JIRA User)
Type	Bug

Environment

macOS 10.12.1, MacBook Pro (Retina, 15-inch, Late 2013)

Additional Detail from JIRA

| | | |------------------|-----------------| |Votes | 0 | |Component/s | Compiler | |Labels | Bug | |Assignee | None | |Priority | Medium | md5: 6f241f59c6c474f8b7917e9b8ab1a787

Issue Description:

I'm doing a simple project of benchamrking custom binary tree implementation in Swift.
This is the code:
https://github.com/ciapasty/word-count/blob/master/word-count/BinaryTreeDictionary.swift

When the generic class type is set to conform to Hashable protocol:

class BinaryTreeDictionary<K: Hashable, V>

and when values are added, the program starts to consume memory.
With huge amounts of data, or any kind of data, used memory increases by aprox. 200 MB per second.

There is no issue when Hashable protocol is changed to Comparable.

[belkadan]

What version of Xcode are you using? How are you performing this benchmarking?

[swift-ci]

Comment by Maciej Eichler (JIRA)

Xcode Version 8.1 (8B62).

The problem appearswhen adding values to the data structure in loop. It's not related to other benchmarking class.

These are methods that are used:

func addValue(_ value: V, forKey key: K) {
        if let root = self.root {
            if let tree = searchTree(root, key: key) {
                tree.value = value
            } else {
                insertTree(root, key: key, value: value, parent: root)
            }
        } else {
            self.root = Tree(key: key, value: value)
        }
    }

private func searchTree(_ tree: Tree<K, V>?, key: K) -> Tree<K, V>? {
        if tree == nil { return nil }
        if tree!.key == key { return tree }
        if key.hashValue < tree!.key.hashValue {
            return searchTree(tree!.leftBranch, key: key)
        } else {
            return searchTree(tree!.rightBranch, key: key)
        }
    }

    private func insertTree(_ tree: Tree<K, V>?, key: K, value: V, parent: Tree<K, V>?) {
        if tree == nil {
            let newTree = Tree<K, V>(key: key, value: value)
            newTree.parentTree = parent

            if key.hashValue < parent!.key.hashValue {
                parent!.leftBranch = newTree
            } else {
                parent!.rightBranch = newTree
            }
        } else {
            if key.hashValue < tree!.key.hashValue {
                insertTree(tree!.leftBranch, key: key, value: value, parent: tree)
            } else {
                insertTree(tree!.rightBranch, key: key, value: value, parent: tree)
            }
        }
    }

I'm tracking memory consumption on Xcode Debug Session.