Расход памяти.
Доклад о потреблении памяти в типичных структурах Java.
Страница 28 содержит кадр с TreeMap.
Расходы на такое дерево: double занимает 24 байта из которых только 8 данных, на корень TreeMap приходится 48 байтов, на запись - 40 байт. В пределе это даёт 82% накладных расходов.
В Хаскеле Double имеет "тэг" (в кавычках ибо STG) и данные, Тэг - это слово. А вот и структура, аналогичная TreeMap:
data Map k a = Tip
| Bin {-# UNPACK #-} !Size !k a !(Map k a) !(Map k a)
Tip - константа, разделяется между всеми деревьями.
Запись конструктора Bin, помимо "тэга конструктора", содержит размер, указатель на ключ, указатель на данные и два указателя на поддеревья, 6 целых чисел. Размер будет избавлен от тэга и будет располагаться непосредствено в Bin, дополнительных 8 байт на размер не будет. Итак, получается 24 байта на запись в дереве.
Итого, 24*(2N-1)+4*N байтов накладных расходов. В пределе для Double (2*8*N байтов ключей и данных) получается 76%. Не вдвое меньше, но всё равно экономия налицо.
Страница 28 содержит кадр с TreeMap.
Расходы на такое дерево: double занимает 24 байта из которых только 8 данных, на корень TreeMap приходится 48 байтов, на запись - 40 байт. В пределе это даёт 82% накладных расходов.
В Хаскеле Double имеет "тэг" (в кавычках ибо STG) и данные, Тэг - это слово. А вот и структура, аналогичная TreeMap:
data Map k a = Tip
| Bin {-# UNPACK #-} !Size !k a !(Map k a) !(Map k a)
Tip - константа, разделяется между всеми деревьями.
Запись конструктора Bin, помимо "тэга конструктора", содержит размер, указатель на ключ, указатель на данные и два указателя на поддеревья, 6 целых чисел. Размер будет избавлен от тэга и будет располагаться непосредствено в Bin, дополнительных 8 байт на размер не будет. Итак, получается 24 байта на запись в дереве.
Итого, 24*(2N-1)+4*N байтов накладных расходов. В пределе для Double (2*8*N байтов ключей и данных) получается 76%. Не вдвое меньше, но всё равно экономия налицо.