Welcome to CluSim’s documentation!
This package (will be) available in PyPI. Just run the following command on terminal to install.
>>> pip install clusim
You can also source the code directly from the github [project page](https://github.com/Hoosier-Clusters/clusim).
We start by importing the required modules
>>> from clusim.clustering import Clustering, print_clustering
>>> import clusim.sim as sim
The simplest way to make a Clustering is to use an elm2clu_dict which maps each element.
>>> c1 = Clustering(elm2clu_dict = {0:[0], 1:[0], 2:[1], 3:[1], 4:[2], 5:[2]})
>>> c2 = Clustering(elm2clu_dict = {0:[0], 1:[1], 2:[1], 3:[1], 4:[1], 5:[2]})
>>> print_clustering(c1)
>>> print_clustering(c2)
Finally, the similarity of the two Clusterings can be found using the Jaccard Index.
>>> sim.jaccard_index(c1, c2)
>>> from clusim.clustering import Clustering, print_clustering
>>> import clusim.sim as sim
>>> c1 = Clustering(elm2clu_dict = {0:[0], 1:[0], 2:[1], 3:[1], 4:[2], 5:[2]})
>>> c2 = Clustering(elm2clu_dict = {0:[0], 1:[1], 2:[1], 3:[1], 4:[1], 5:[2]})
The basic element-centric similarity score with a fixed alpha:
>>> sim.element_sim(c1, c2, alpha = 0.9)
We can also get the element scores. Note that since non-numberic elements are allowed, the element scores returns a dict which maps the elements to the index in the elementScore array.
>>> elementScores, relabeled_elements = sim.element_sim_elscore(c1, c2, alpha = 0.9)
clusim.clustering.
Clustering
(elm2clu_dict=None, clu2elm_dict=None, hier_graph=None)¶Base class for clusterings.
| Parameters: |
|
|---|
copy
()¶Return a deep copy of the clustering.
| Returns: | deep copy of the clustering |
|---|
>>> from clusim.clustering import Clustering, print_clustering
>>> clu = clusim.Clustering()
>>> clu2 = clu.copy()
>>> print_clustering(clu)
>>> print_clustering(clu)
from_elm2clu_dict
(elm2clu_dict)¶This method creates a clustering from an elm2clu_dict dictionary: { elementid: [clu1, clu2, … ] } where each element is a key with value a list of clusters to which it belongs. Clustering features are then calculated.
| Parameters: | elm2clu_dict (dict) – { elementid: [clu1, clu2, … ] } |
|---|
>>> from clusim.clustering import Clustering, print_clustering
>>> elm2clu_dict = {0:[0], 1:[0], 2:[0,1], 3:[1], 4:[2], 5:[2]}
>>> clu = Clustering()
>>> clu.from_elm2clu_dict(elm2clu_dict)
>>> print_clustering(clu)
from_clu2elm_dict
(clu2elm_dict)¶This method creates a clustering from an clu2elm_dict dictionary: { clusid: [el1, el22, … ] } where each cluster is a key with value a list of elements which belong to it. Clustering features are then calculated.
| Parameters: | clu2elm_dict (dict) – { clusid: [el1, el2, … ] } |
|---|
>>> from clusim.clustering import Clustering, print_clustering
>>> clu2elm_dict = {0:[0,1,2], 1:[2,3], 2:[4,5]}
>>> clu = Clustering()
>>> clu.from_clu2elm_dict(clu2elm_dict)
>>> print_clustering(clu)
from_cluster_list
(cluster_list)¶This method creates a clustering from a cluster list: [ [el1, el2, …], [el5, …], … ], a list of lists, where each inner list corresponds to the elements in a cluster. Clustering features are then calculated.
| Parameters: | cluster_list (list) – list of lists [ [el1, el2, …], [el5, …], … ] |
|---|
>>> from clusim.clustering import Clustering, print_clustering
>>> cluster_list = [ [0,1,2], [2,3], [4,5]]
>>> clu = Clustering()
>>> clu.from_cluster_list(cluster_list)
>>> print_clustering(clu)
to_cluster_list
()¶This method returns a clustering in cluster list format: [ [el1, el2, …], [el5, …], … ], a list of lists, where each inner list corresponds to the elements in a cluster.
| Returns: | cluster_list : list of lists, [ [el1, el2, …], [el5, …], … ] |
|---|
from_membership_list
(membership_list)¶This method creates a clustering from a membership list: [ clu_for_el1, clu_for_el2, … ], a list of cluster names where the ith entry corresponds to the cluster membership of the ith element. Clustering features are then calculated.
Note
Membership Lists can only represent partitions (no overlaps)
| Parameters: | membership_list (list) – list of cluster names clu_for_el1, clu_for_el2, … ] |
|---|
>>> from clusim.clustering import Clustering, print_clustering
>>> membership_list = [0,0,0,1,2,2]
>>> clu = Clustering()
>>> clu.from_membership_list(membership_list)
>>> print_clustering(clu)
to_membership_list
()¶This method returns the clustering as a membership list: [ clu_for_el1, clu_for_el2, … ], a list of cluster names the ith entry corresponds to the cluster membership of the ith element.
Note
Membership Lists can only represent partitions (no overlaps)
| Returns: | list of element memberships, [ clu_for_el1, clu_for_el2, … ] |
|---|
clustering_from_igraph_cover
(igraphcover)¶This method creates a clustering from an igraph VertexCover object.
See the igraph.Cover.VertexCover
class.
Clustering features are then calculated.
| Parameters: | igraphcover (igraph.Cover.VertexCover) – the igraph VertexCover |
|---|
to_clu2elm_dict
()¶Create a clu2elm_dict: {clusterid: [el1, el2, … ]} from the stored elm2clu_dict.
| Returns: | dict |
|---|
to_elm2clu_dict
()¶Create a elm2clu_dict: {elementid: [clu1, clu2, … ]} from the stored clu2elm_dict.
| Returns: | dict |
|---|
find_clu_size_seq
()¶This method finds the cluster size sequence for the clustering.
| Returns: | list of integers A list where the ith entry corresponds to the size of the ith cluster. |
|---|
>>> from clusim.clustering import Clustering, print_clustering
>>> elm2clu_dict = {0:[0], 1:[0], 2:[0,1], 3:[1], 4:[2], 5:[2]}
>>> clu = Clustering(elm2clu_dict = elm2clu_dict)
>>> print("Cluster Size Sequence:", clu.find_clu_size_seq())
* Cluster Size Sequence: [3, 2, 2]
find_num_overlap
()¶This method finds the number of elements which are in more than one cluster in the clustering.
| Returns: | The number of elements in at least two clusters. |
|---|
>>> from clusim.clustering import Clustering, print_clustering
>>> elm2clu_dict = {0:[0], 1:[0], 2:[0,1], 3:[1], 4:[2], 5:[2]}
>>> clu = Clustering(elm2clu_dict = elm2clu_dict)
>>> print("Overlap size:", clu.find_num_overlap())
* Overlap size: 1
merge_clusters
(c1, c2, new_name=None)¶This method merges the elements in two clusters from the clustering. The merged clustering will be named new_name if provided, otherwise it will assume the name of cluster c1.
| Returns: | self |
|---|
>>> from clusim.clustering import Clustering, print_clustering
>>> elm2clu_dict = {0:[0], 1:[0], 2:[0], 3:[1], 4:[2], 5:[2]}
>>> clu = Clustering(elm2clu_dict = elm2clu_dict)
>>> print_clustering(clu)
>>> clu.merge_clusters(1,2, new_name = 3)
>>> print_clustering(clu)
downstream_elements
(cluster)¶This method finds all elements contained in a cluster from a hierarchical clustering by visiting all downstream clusters and adding their elements.
| Parameters: | cluster – the name of the parent cluster |
|---|---|
| Returns: | element list |
from_scipy_linkage
(linkage_matrix, dist_rescaled=False)¶This method creates a clustering from a scipy linkage object resulting from the agglomerative hierarchical clustering. Clustering features are then calculated.
| Parameters: |
|
|---|
>>> from clusim.clustering import Clustering, print_clustering
>>> from scipy.cluster.hierarchy import dendrogram, linkage
>>> import numpy as np
>>> np.random.seed(42)
>>> data1 = np.random.multivariate_normal([10, 0], [[3, 1], [1, 4]],
size=[100,])
>>> data2 = np.random.multivariate_normal([0, 20], [[3, 1], [1, 4]],
size=[50,])
>>> Xdata = np.concatenate((data1, data2), )
>>> Z = linkage(X, 'ward')
>>> clu = Clustering()
>>> clu.from_scipy_linkage(Z, dist_rescaled=False)
clusim.clustering.
ClusterError
(expression, message)¶clusim.clustering.
Clustering
(elm2clu_dict=None, clu2elm_dict=None, hier_graph=None)Base class for clusterings.
| Parameters: |
|
|---|
copy
()Return a deep copy of the clustering.
| Returns: | deep copy of the clustering |
|---|
>>> from clusim.clustering import Clustering, print_clustering
>>> clu = clusim.Clustering()
>>> clu2 = clu.copy()
>>> print_clustering(clu)
>>> print_clustering(clu)
from_elm2clu_dict
(elm2clu_dict)This method creates a clustering from an elm2clu_dict dictionary: { elementid: [clu1, clu2, … ] } where each element is a key with value a list of clusters to which it belongs. Clustering features are then calculated.
| Parameters: | elm2clu_dict (dict) – { elementid: [clu1, clu2, … ] } |
|---|
>>> from clusim.clustering import Clustering, print_clustering
>>> elm2clu_dict = {0:[0], 1:[0], 2:[0,1], 3:[1], 4:[2], 5:[2]}
>>> clu = Clustering()
>>> clu.from_elm2clu_dict(elm2clu_dict)
>>> print_clustering(clu)
from_clu2elm_dict
(clu2elm_dict)This method creates a clustering from an clu2elm_dict dictionary: { clusid: [el1, el22, … ] } where each cluster is a key with value a list of elements which belong to it. Clustering features are then calculated.
| Parameters: | clu2elm_dict (dict) – { clusid: [el1, el2, … ] } |
|---|
>>> from clusim.clustering import Clustering, print_clustering
>>> clu2elm_dict = {0:[0,1,2], 1:[2,3], 2:[4,5]}
>>> clu = Clustering()
>>> clu.from_clu2elm_dict(clu2elm_dict)
>>> print_clustering(clu)
from_cluster_list
(cluster_list)This method creates a clustering from a cluster list: [ [el1, el2, …], [el5, …], … ], a list of lists, where each inner list corresponds to the elements in a cluster. Clustering features are then calculated.
| Parameters: | cluster_list (list) – list of lists [ [el1, el2, …], [el5, …], … ] |
|---|
>>> from clusim.clustering import Clustering, print_clustering
>>> cluster_list = [ [0,1,2], [2,3], [4,5]]
>>> clu = Clustering()
>>> clu.from_cluster_list(cluster_list)
>>> print_clustering(clu)
to_cluster_list
()This method returns a clustering in cluster list format: [ [el1, el2, …], [el5, …], … ], a list of lists, where each inner list corresponds to the elements in a cluster.
| Returns: | cluster_list : list of lists, [ [el1, el2, …], [el5, …], … ] |
|---|
from_membership_list
(membership_list)This method creates a clustering from a membership list: [ clu_for_el1, clu_for_el2, … ], a list of cluster names where the ith entry corresponds to the cluster membership of the ith element. Clustering features are then calculated.
Note
Membership Lists can only represent partitions (no overlaps)
| Parameters: | membership_list (list) – list of cluster names clu_for_el1, clu_for_el2, … ] |
|---|
>>> from clusim.clustering import Clustering, print_clustering
>>> membership_list = [0,0,0,1,2,2]
>>> clu = Clustering()
>>> clu.from_membership_list(membership_list)
>>> print_clustering(clu)
to_membership_list
()This method returns the clustering as a membership list: [ clu_for_el1, clu_for_el2, … ], a list of cluster names the ith entry corresponds to the cluster membership of the ith element.
Note
Membership Lists can only represent partitions (no overlaps)
| Returns: | list of element memberships, [ clu_for_el1, clu_for_el2, … ] |
|---|
clustering_from_igraph_cover
(igraphcover)This method creates a clustering from an igraph VertexCover object.
See the igraph.Cover.VertexCover
class.
Clustering features are then calculated.
| Parameters: | igraphcover (igraph.Cover.VertexCover) – the igraph VertexCover |
|---|
to_clu2elm_dict
()Create a clu2elm_dict: {clusterid: [el1, el2, … ]} from the stored elm2clu_dict.
| Returns: | dict |
|---|
to_elm2clu_dict
()Create a elm2clu_dict: {elementid: [clu1, clu2, … ]} from the stored clu2elm_dict.
| Returns: | dict |
|---|
find_clu_size_seq
()This method finds the cluster size sequence for the clustering.
| Returns: | list of integers A list where the ith entry corresponds to the size of the ith cluster. |
|---|
>>> from clusim.clustering import Clustering, print_clustering
>>> elm2clu_dict = {0:[0], 1:[0], 2:[0,1], 3:[1], 4:[2], 5:[2]}
>>> clu = Clustering(elm2clu_dict = elm2clu_dict)
>>> print("Cluster Size Sequence:", clu.find_clu_size_seq())
* Cluster Size Sequence: [3, 2, 2]
find_num_overlap
()This method finds the number of elements which are in more than one cluster in the clustering.
| Returns: | The number of elements in at least two clusters. |
|---|
>>> from clusim.clustering import Clustering, print_clustering
>>> elm2clu_dict = {0:[0], 1:[0], 2:[0,1], 3:[1], 4:[2], 5:[2]}
>>> clu = Clustering(elm2clu_dict = elm2clu_dict)
>>> print("Overlap size:", clu.find_num_overlap())
* Overlap size: 1
merge_clusters
(c1, c2, new_name=None)This method merges the elements in two clusters from the clustering. The merged clustering will be named new_name if provided, otherwise it will assume the name of cluster c1.
| Returns: | self |
|---|
>>> from clusim.clustering import Clustering, print_clustering
>>> elm2clu_dict = {0:[0], 1:[0], 2:[0], 3:[1], 4:[2], 5:[2]}
>>> clu = Clustering(elm2clu_dict = elm2clu_dict)
>>> print_clustering(clu)
>>> clu.merge_clusters(1,2, new_name = 3)
>>> print_clustering(clu)
downstream_elements
(cluster)This method finds all elements contained in a cluster from a hierarchical clustering by visiting all downstream clusters and adding their elements.
| Parameters: | cluster – the name of the parent cluster |
|---|---|
| Returns: | element list |
from_scipy_linkage
(linkage_matrix, dist_rescaled=False)This method creates a clustering from a scipy linkage object resulting from the agglomerative hierarchical clustering. Clustering features are then calculated.
| Parameters: |
|
|---|
>>> from clusim.clustering import Clustering, print_clustering
>>> from scipy.cluster.hierarchy import dendrogram, linkage
>>> import numpy as np
>>> np.random.seed(42)
>>> data1 = np.random.multivariate_normal([10, 0], [[3, 1], [1, 4]],
size=[100,])
>>> data2 = np.random.multivariate_normal([0, 20], [[3, 1], [1, 4]],
size=[50,])
>>> Xdata = np.concatenate((data1, data2), )
>>> Z = linkage(X, 'ward')
>>> clu = Clustering()
>>> clu.from_scipy_linkage(Z, dist_rescaled=False)
clusim.clustering.
ClusterError
(expression, message)clusim.clustering.
print_clustering
(clustering)¶A function to print a clustering. Clusters are seperated by ‘|’. The fuction will only print the leaf layer of a Hierarchical Clustering.
| Parameters: | clustering (Clsutering) – The clustering to print |
|---|
>>> import clusim.clugen as clugen
>>> from clusim.clustering import print_clustering
>>> clu = clugen.make_equal_clustering(n_elements = 9, n_clusters = 3)
>>> print_clustering(clu)
clusim.clugen.
make_equal_clustering
(n_elements, n_clusters)¶This function creates a random clustering with equally sized clusters. If n_elements % n_clusters != 0, cluster sizes will differ by one element.
| Parameters: |
|
|---|---|
| Returns: | The new clustering with equally sized clusters. |
>>> import clusim.clugen as clugen
>>> from clusim.clustering import print_clustering
>>> clu = clugen.make_equal_clustering(n_elements = 9, n_clusters = 3)
>>> print_clustering(clu)
clusim.clugen.
make_random_clustering
(n_elements=1, n_clusters=1, clu_size_seq=[1, 2], random_model='all', tol=1e-15)¶This function creates a random clustering according to one of three random models. It is a wrapper around the specific functions for each random model.
| Parameters: |
|
|---|---|
| Returns: | The new clustering. |
>>> import clusim.clugen as clugen
>>> from clusim.clustering import print_clustering
>>> clu = clugen.make_random_clustering(n_elements = 9, n_clusters = 3,
random_model = 'num')
>>> print_clustering(clu)
clusim.clugen.
make_singleton_clustering
(n_elements)¶This function creates a clustering with each element in its own cluster.
| Parameters: | n_elements (int) – The number of elements |
|---|---|
| Returns: | The new clustering. |
>>> import import clusim.clugen as clugen
>>> from clusim.clustering import print_clustering
>>> clu = clugen.make_singleton_clustering(n_elements = 9)
>>> print_clustering(clu)
clusim.clugen.
make_random_dendrogram
(n_elements)¶This function creates a random Hierarchical Clustering.
:param int n_elements The number of elements
| Returns: | The new clustering. |
|---|
clusim.clugen.
shuffle_memberships
(clustering, percent=1.0)¶This function creates a new clustering by shuffling the element memberships from the original clustering.
| Parameters: |
|
|---|---|
| Returns: | The new clustering. |
>>> import clusim.clugen as clugen
>>> from clusim.clustering import print_clustering
>>> orig_clu = clugen.make_random_clustering(n_elements = 9, n_clusters = 3,
random_model = 'num')
>>> print_clustering(orig_clu)
>>> shuffle_clu = clugen.shuffle_memberships(orig_clu, percent = 0.5)
>>> print_clustering(shuffle_clu)
clusim.clugen.
shuffle_memberships_pa
(clustering, n_steps=1, constant_num_clusters=True)¶This function creates a new clustering by shuffling the element memberships from the original clustering according to the preferential attachment model.
See [GA17] for a detailed explaination of the preferential attachment model.
| Parameters: |
|
|---|---|
| Returns: | The new clustering with shuffled memberships. |
>>> import clusim.clugen as clugen
>>> from clusim.clustering import print_clustering
>>> orig_clu = clugen.make_random_clustering(n_elements=9, n_clusters=3,
random_model='num')
>>> print_clustering(orig_clu)
>>> shuffle_clu = clugen.shuffle_memberships_pa(orig_clu, n_steps=10,
constant_num_clusters=True)
>>> print_clustering(shuffle_clu)
clusim.clugen.
generate_random_partition_all
(n_elements, tol=1e-15)¶This function creates a random clustering according to the ‘All’ random model by uniformly selecting a clustering from the ensemble of all clusterings with n_elements.
| Parameters: |
|
|---|---|
| Returns: | The randomly genderated clustering. |
>>> import clusim.clugen as clugen
>>> from clusim.clustering import print_clustering
>>> clu = clugen.generate_random_partition_all(n_elements = 9)
>>> print_clustering(clu)
clusim.clugen.
enumerate_random_partition_num
(n_elements, n_clusters)¶A generator for every partition in ‘Num’, the ensemble of all clusterings with n_elements grouped into n_clusters, non-empty clusters.
Based on the solution provided by Adeel Zafar Soomro: a link.
which was itself based on the algorithm from Knuth: (Algorithm U) is described by Knuth in the Art of Computer Programming, Volume 4, Fascicle 3B
| Parameters: |
|
|---|---|
| Returns: | The new clustering as a cluster list. |
>>> import clusim.clugen as clugen
>>> from clusim.clustering import print_clustering
>>> for clu in clugen.clustering_ensemble_generator_num(n_elements=5, n_clusters=3):
>>> print_clustering(clu)
The different clustering similarity measures available.
clusim.sim.
contingency_table
(clustering1, clustering2)¶This function creates the contigency table between two clusterings.
| Parameters: |
|
|---|---|
| Returns: | The clustering1.n_clusters by clustering2.n_clusters contigency table as a list of lists |
>>> import clusim.clugen as clugen
>>> clustering1 = clugen.make_random_clustering(n_elements=9, n_clusters=3,
random_model = 'num')
>>> clustering2 = clugen.make_random_clustering(n_elements=9, n_clusters=3,
random_model = 'num')
>>> cont_table = contingency_table(clustering1, clustering2)
>>> print(cont_table)
clusim.sim.
count_pairwise_cooccurence
(clustering1, clustering2)¶This function finds the pairwise cooccurence counts between two clusterings.
| Parameters: |
|
|---|---|
| Returns: |
|
>>> import clusim.clugen as clugen
>>> import clusim.sim as sim
>>> from clusim.clustering import print_clustering
>>> clustering1 = clugen.make_random_clustering(n_elements=9, n_clusters=3,
random_model='num')
>>> clustering2 = clugen.make_random_clustering(n_elements=9, n_clusters=3,
random_model='num')
>>> N11, N10, N01, N00 = sim.count_pairwise_cooccurence(clustering1,
clustering2)
>>> print_clustering(clustering1)
>>> print_clustering(clustering2)
>>> print(N11,
"element pairs assigned to the same clusters in both clusterings")
>>> print(N10,
"element pairs assigned to the same clusters in clustering1, but "
"different clusters in clustering2")
>>> print(N01, "element pairs assigned to different clusters in "
"clustering1, but the same clusters in clustering2")
>>> print(N00, "element pairs assigned to different clusters in both "
"clusterings")
clusim.sim.
jaccard_index
(clustering1, clustering2)¶This function calculates the Jaccard index between two clusterings [Jac12].
J = N11/(N11+N10+N01)
| Parameters: |
|
|---|---|
| Returns: | The Jaccard index (between 0.0 and 1.0) |
>>> import clusim.clugen as clugen
>>> import clusim.sim as sim
>>> clustering1 = clugen..make_random_clustering(n_elements=9,
n_clusters=3,
random_model='num')
>>> clustering2 = clugen.make_random_clustering(n_elements=9,
n_clusters=3,
random_model='num')
>>> print(sim.jaccard_index(clustering1, clustering2) )
clusim.sim.
rand_index
(clustering1, clustering2)¶This function calculates the Rand index between two clusterings [Ran71].
RI = (N11 + N00) / (N11 + N10 + N01 + N00)
| Parameters: |
|
|---|---|
| Returns: | The Rand index (between 0.0 and 1.0) |
>>> import clusim.clugen as clugen
>>> import clusim.sim as sim
>>> clustering1 = clugen..make_random_clustering(n_elements=9, n_clusters=3,
random_model='num')
>>> clustering2 = clugen.make_random_clustering(n_elements=9, n_clusters=3,
random_model='num')
>>> print(sim.rand_index(clustering1, clustering2))
clusim.sim.
fowlkes_mallows_index
(clustering1, clustering2)¶This function calculates the Fowlkes and Mallows index between two clusterings [FM83].
FM = N11 / sqrt( (N11 + N10) * (N11 + N01) )
| Parameters: |
|
|---|---|
| Returns: | The Fowlkes and Mallows index (between 0.0 and 1.0) |
>>> import clusim.clugen as clugen
>>> import clusim.sim as sim
>>> clustering1 = clugen.make_random_clustering(n_elements=9, n_clusters=3,
random_model='num')
>>> clustering2 = clugen.make_random_clustering(n_elements=9, n_clusters=3,
random_model='num')
>>> print(sim.fowlkes_mallows_index(clustering1, clustering2))
clusim.sim.
fmeasure
(clustering1, clustering2)¶This function calculates the F-measure between two clusterings.
Also known as: Czekanowski index Dice Symmetric index Sorensen index
F = 2*N11 / (2*N11 + N10 + N01)
| Parameters: |
|
|---|---|
| Returns: | The F-measure (between 0.0 and 1.0) |
>>> import clusim.clugen as clugen
>>> import clusim.sim as sim
>>> clustering1 = clugen.make_random_clustering(n_elements=9, n_clusters=3,
random_model='num')
>>> clustering2 = clugen.make_random_clustering(n_elements=9, n_clusters=3,
random_model='num')
>>> print(sim.fmeasure(clustering1, clustering2))
clusim.sim.
purity_index
(clustering1, clustering2)¶This function calculates the Purity index between two clusterings.
| Parameters: |
|
|---|---|
| Returns: | The Purity index (between 0.0 and 1.0) |
>>> import clusim.clugen as clugen
>>> import clusim.sim as sim
>>> clustering1 = clugen.make_random_clustering(n_elements=9, n_clusters=3,
random_model='num')
>>> clustering2 = clugen.make_random_clustering(n_elements=9, n_clusters=3,
random_model='num')
>>> print(sim.purity_index(clustering1, clustering2))
clusim.sim.
classification_error
(clustering1, clustering2)¶This function calculates the Jaccard index between two clusterings.
CE = 1 - PI
| Parameters: |
|
|---|---|
| Returns: | The Classification Error (between 0.0 and 1.0) |
Note
CE is a distance measure, it is 0 for identical clusterings
>>> import clusim.clugen as clugen
>>> import clusim.sim as sim
>>> clustering1 = clugen.make_random_clustering(n_elements=9, n_clusters=3,
random_model='num')
>>> clustering2 = clugen.make_random_clustering(n_elements=9, n_clusters=3,
random_model='num')
>>> print(sim.classification_error(clustering1, clustering2))
clusim.sim.
czekanowski_index
(clustering1, clustering2)¶This function calculates the Czekanowski index between two clusterings.
See Fmeasure
clusim.sim.
dice_index
(clustering1, clustering2)¶This function calculates the Dice index between two clusterings.
See Fmeasure
clusim.sim.
sorensen_index
(clustering1, clustering2)¶This function calculates the Sorensen index between two clusterings.
See Fmeasure
clusim.sim.
rogers_tanimoto_index
(clustering1, clustering2)¶This function calculates the Rogers and Tanimoto index between two clusterings.
RT = (N11 + N00)/(N11 + 2*(N10+N01) + N00)
| Parameters: |
|
|---|---|
| Returns: | The Rogers and Tanimoto index (between 0.0 and 1.0) |
>>> import clusim.clugen as clugen
>>> import clusim.sim as sim
>>> clustering1 = clugen.make_random_clustering(n_elements=9, n_clusters=3,
random_model='num')
>>> clustering2 = clugen.make_random_clustering(n_elements=9, n_clusters=3,
random_model='num')
>>> print(sim.rogers_tanimoto_index(clustering1, clustering2))
clusim.sim.
southwood_index
(clustering1, clustering2)¶calculate the southwood index
N11 / (N10 + N01)
| Parameters: |
|
|---|---|
| Returns: | The Southwood index (between 0 and 1.0) |
>>> import clusim.clugen as clugen
>>> import clusim.sim as sim
>>> clustering1 = clugen.make_random_clustering(n_elements=9, n_clusters=3,
random_model='num')
>>> clustering2 = clugen.make_random_clustering(n_elements=9, n_clusters=3,
random_model='num')
>>> print(sim.southwood_index(clustering1, clustering2))
clusim.sim.
pearson_correlation
(clustering1, clustering2)¶This function calculates the Pearson Correlation between two clusterings.
PC = (N11*N00 - N01*N10) / ((N11+N10) * (N11+N01) * (N00+N10) * (N00+N01))
| Parameters: |
|
|---|---|
| Returns: | The Pearson Correlation (between -1.0 and 1.0) |
>>> import clusim.clugen as clugen
>>> import clusim.sim as sim
>>> clustering1 = clugen.make_random_clustering(n_elements=9, n_clusters=3,
random_model='num')
>>> clustering2 = clugen.make_random_clustering(n_elements=9, n_clusters=3,
random_model='num')
>>> print(sim.pearson_correlation(clustering1, clustering2))
clusim.sim.
nmi
(clustering1, clustering2, norm_type='sum')¶This function calculates the Normalized Mutual Information (NMI) between two clusterings [DDiazGDA05].
NMI = (S(c1) + S(c2) - S(c1, c2)) / norm(c1, c2)
where S(c1) is the Shannon Entropy of the clustering size distrubtion, S(c1, c2) is the Shannon Entropy of the join clustering size distrubtion, and norm(c1,c2) is a normalizetion term.
| Parameters: |
|
|---|---|
| Returns: | The Normalized Mutual Information index (between 0.0 and inf) |
>>> import clusim.clugen as clugen
>>> import clusim.sim as sim
>>> clustering1 = clugen.make_random_clustering(n_elements=9, n_clusters=3,
random_model='num')
>>> clustering2 = clugen.make_random_clustering(n_elements=9, n_clusters=3,
random_model='num')
>>> print(sim.nmi(clustering1, clustering2, norm_type='sum'))
>>> print(sim.nmi(clustering1, clustering2, norm_type='max'))
>>> print(sim.nmi(clustering1, clustering2, norm_type='min'))
>>> print(sim.nmi(clustering1, clustering2, norm_type='sqrt'))
clusim.sim.
vi
(clustering1, clustering2, norm_type='none')¶This function calculates the Variation of Information (VI) between two clusterings [Mei03].
VI is technically a distance measure and can assume values in the range [0, inf), where 0 denotes identical clusterings.
VI = 2*S(c1, c2) - S(c1) - S(c2)
where S(c1) is the Shannon Entropy of the clustering size distrubtion, and S(c1, c2) is the Shannon Entropy of the join clustering size distrubtion.
The VI can be transformed into a clustering similarity measure via the appropraite normalization.
VI_{sim} = 1 - 0.5*((S(c1,c2) - S(c1))/S(c2) + (S(c1,c2) - S(c2))/S(c1))
| Parameters: |
|
|---|
| Returns: | The Variation of Information index (between 0.0 and inf) |
|---|
>>> import clusim.clugen as clugen
>>> import clusim.sim as sim
>>> clustering1 = clugen.make_random_clustering(n_elements=9, n_clusters=3,
random_model='num')
>>> clustering2 = clugen.make_random_clustering(n_elements=9, n_clusters=3,
random_model='num')
>>> print(sim.vi(clustering1, clustering2))
clusim.sim.
corrected_chance
(clustering1, clustering2, measure='jaccard_index', random_model='perm', norm_type='sum', n_samples=100)¶This function calculates the adjusted Similarity for one of six random models.
Note
Clustering 2 is considered the gold-standard clustering for one-sided expectations
| Parameters: |
|
|---|
| Returns: | The adjusted Similarity measure |
|---|
>>> import clusim.clugen as clugen
>>> import clusim.sim as sim
>>> clustering1 = clugen.make_random_clustering(n_elements=9, n_clusters=3,
random_model='all')
>>> clustering2 = clugen.make_random_clustering(n_elements=9, n_clusters=3,
random_model='all')
>>> print(sim.corrected_chance(clustering1, clustering2, measure='jaccard_index',
random_model='all'))
>>> print(sim.corrected_chance(clustering1, clustering2, measure='jaccard_index',
random_model='all1'))
>>> print(sim.corrected_chance(clustering1, clustering2, measure='jaccard_index',
random_model='num'))
>>> print(sim.corrected_chance(clustering1, clustering2, measure='jaccard_index',
random_model='num1'))
>>> print(sim.corrected_chance(clustering1, clustering2, measure='jaccard_index',
random_model='perm'))
>>> print(sim.corrected_chance(clustering1, clustering2, measure='jaccard_index',
random_model='perm1'))
clusim.sim.
sample_expected_sim
(clustering1, clustering2, measure='jaccard_index', random_model='perm', n_samples=1, keep_samples=False)¶This function calculates the expected Similarity for all pair-wise comparisons between Clusterings drawn from one of six random models.
Note
Clustering 2 is considered the gold-standard clustering for one-sided expectations
| Parameters: |
|
|---|---|
| Returns: | The expected Similarity measure for all pair-wise comparisons under a random model |
>>> import clusim.clugen as clugen
>>> import clusim.sim as sim
>>> c1 = clugen.make_random_clustering(n_elements=9, n_clusters=3, random_model='all')
>>> c2 = clugen.make_random_clustering(n_elements=9, n_clusters=3, random_model='all')
>>> print(sim.sample_expected_sim(c1, c2, measure='jaccard_index', random_model='all', n_samples=50))
>>> print(sim.sample_expected_sim(c1, c2, measure='jaccard_index', random_model='all1', n_samples=50))
>>> print(sim.sample_expected_sim(c1, c2, measure='jaccard_index', random_model='num', n_samples=50))
>>> print(sim.sample_expected_sim(c1, c2, measure='jaccard_index', random_model='num1', n_samples=50))
>>> print(sim.sample_expected_sim(c1, c2, measure='jaccard_index', random_model='perm', n_samples=50))
>>> print(sim.sample_expected_sim(c1, c2, measure='jaccard_index', random_model='perm1', n_samples=50) )
clusim.sim.
expected_rand_index
(n_elements, random_model='num', n_clusters1=2, n_clusters2=2, clu_size_seq1=None, clu_size_seq2=None)¶This function calculates the expectation of the Rand index between all pairs of clusterings drawn from one of six random models.
See [HA85] and [GA17] for a detailed derivation and explaination of the different random models.
Note
Clustering 2 is considered the gold-standard clustering for one-sided expectations
| Parameters: |
|
|---|---|
| Returns: | The expected Rand index (between 0.0 and 1.0) |
>>> import clusim.sim as sim
>>> print(sim.expected_rand_index(n_elements=5, random_model='all'))
>>> print(sim.expected_rand_index(n_elements=5, random_model='all1',
clu_size_seq2=[1,1,3]))
>>> print(sim.expected_rand_index(n_elements=5, , random_model='num',
n_clusters1=2, n_clusters2=3))
>>> print(sim.expected_rand_index(n_elements=5, random_model='num1',
n_clusters1=2, clu_size_seq2=[1,1,3]))
>>> print(sim.expected_rand_index(n_elements=5, random_model='perm',
clu_size_seq1=[2,3],
clu_size_seq2=[1,1,3]))
>>> print(sim.expected_rand_index(n_elements=5, random_model='perm1',
clu_size_seq1=[2,3],
clu_size_seq2=[1,1,3]))
clusim.sim.
adjrand_index
(clustering1, clustering2, random_model='perm')¶This function calculates the adjusted Rand index for one of six random models.
See [HA85] and [GA17] for a detailed derivation and explaination of the different random models.
Note
Clustering 2 is considered the gold-standard clustering for one-sided expectations
| Parameters: |
|
|---|---|
| Returns: | The adjusted_rand Rand index |
>>> import clusim.clugen as clugen
>>> import clusim.sim as sim
>>> clustering1 = clugen.make_random_clustering(n_elements=9, n_clusters=3,
random_model='all')
>>> clustering2 = clugen.make_random_clustering(n_elements=9, n_clusters=3,
random_model='all')
>>> print(sim.adjrand_index(clustering1, clustering2,
random_model='all'))
>>> print(sim.adjrand_index(clustering1, clustering2,
random_model='all1'))
>>> print(sim.adjrand_index(clustering1, clustering2,
random_model='num'))
>>> print(sim.adjrand_index(clustering1, clustering2,
random_model='num1'))
>>> print(sim.adjrand_index(clustering1, clustering2,
random_model='perm'))
>>> print(sim.adjrand_index(clustering1, clustering2,
random_model='perm1'))
clusim.sim.
adj_mi
(clustering1, clustering2, random_model='perm', norm_type='sum', logbase=2)¶This function calculates the adjusted Mutual Information for one of six random models.
See [GA17] for a detailed derivation and explaination of the different random models.
Note
Clustering 2 is considered the gold-standard clustering for one-sided expectations
| Parameters: |
|
|---|---|
| Returns: | The adjusted Mutual Information |
>>> import clusim.clugen as clugen
>>> import clusim.sim as sim
>>> clustering1 = clugen.make_random_clustering(n_elements=9, n_clusters=3,random_model='all')
>>> clustering2 = clugen.make_random_clustering(n_elements=9, n_clusters=3,random_model='all')
>>> print(sim.adj_mi(clustering1, clustering2, random_model='all'))
>>> print(sim.adj_mi(clustering1, clustering2, random_model='all1'))
>>> print(sim.adj_mi(clustering1, clustering2,random_model='num'))
>>> print(sim.adj_mi(clustering1, clustering2,random_model='num1'))
>>> print(sim.adj_mi(clustering1, clustering2,random_model='perm'))
>>> print(sim.adj_mi(clustering1, clustering2,random_model='perm1'))
clusim.sim.
expected_mi
(n_elements, n_clusters1=2, n_clusters2=2, clu_size_seq1=None, clu_size_seq2=None, logbase=2, random_model='num')¶This function calculates the expectation of the Mutual Informaiton between all pairs of clusterings drawn from one of six random models.
See [GA17] for a detailed derivation and explaination of the different random models.
Note
Clustering 2 is considered the gold-standard clustering for one-sided expectations
| Parameters: |
|
|---|---|
| Returns: | The expected MI (between 0.0 and inf) |
>>> import clusim.sim as sim
>>> print(sim.expected_mi(n_elements=5, random_model='all'))
>>> print(sim.expected_mi(n_elements=5, random_model='all1',
clu_size_seq2=[1,1,3]))
>>> print(sim.expected_mi(n_elements=5, , random_model='num',
n_clusters1=2, n_clusters2=3))
>>> print(sim.expected_mi(n_elements=5, random_model='num1',
n_clusters1=2, clu_size_seq2=[1,1,3]))
>>> print(sim.expected_mi(n_elements=5, random_model='perm',
clu_size_seq1=[2,3],
clu_size_seq2=[1,1,3]))
>>> print(sim.expected_mi(n_elements=5, random_model='perm1',
clu_size_seq1=[2,3],
clu_size_seq2=[1,1,3]))
clusim.sim.
onmi
(clustering1, clustering2)¶This function calculates the overlaping normalized mututal information.
See [LFK09] for a detailed derivation and explaination of the measure.
| Parameters: |
|
|---|---|
| Returns: | the overlaping normalized mutual information |
clusim.sim.
omega_index
(clustering1, clustering2)¶This function calculates the omega index between two clusterings.
See [CD88] for a detailed derivation and explaination of the measure.
| Parameters: |
|
|---|---|
| Returns: | the omega index |
clusim.sim.
geometric_accuracy
(clustering1, clustering2)¶This function calculates the geometric accuracy between two (overlapping) clusterings.
See [NYP12] for a detailed derivation and explaination of the measure.
| Parameters: |
|
|---|---|
| Returns: | the geometric accuracy |
clusim.sim.
overlap_quality
(clustering1, clustering2)¶This function calculates the overlap quality between two (overlapping) clusterings.
See [ABL10] for a detailed derivation and explaination of the measure.
| Parameters: |
|
|---|---|
| Returns: | the overlap quality |
clusim.clusimelement.
element_sim
(clustering1, clustering2, alpha=0.9, r=1.0, r2=None, rescale_path_type='max')¶The element-centric clustering similarity.
See [GWHA18] for a detailed explaination of the measure.
| Parameters: |
|
|---|---|
| Returns: | The element-wise similarity between the two clusterings |
>>> import clusim.sim as sim
>>> from clusim.clustering import Clustering
>>> clustering1 = Clustering(elm2clu_dict={0:[0], 1:[0], 2:[0,1],
3:[1], 4:[2], 5:[2]})
>>> clustering2 = Clustering(elm2clu_dict={0:[0,2], 1:[0], 2:[0,1],
3:[1], 4:[2], 5:[1,2]})
>>> print(sim.element_sim(clustering1, clustering2, alpha=0.9))
clusim.clusimelement.
element_sim_elscore
(clustering1, clustering2, alpha=0.9, r=1.0, r2=None, rescale_path_type='max', relabeled_elements=None)¶The element-centric clustering similarity for each element.
See [GWHA18] for a detailed explaination of the measure.
| Parameters: |
|
|---|---|
| Returns: | The element-centric similarity between the two clusterings for each element as a 1d numpy array |
| Returns: | a dict mapping each element to its index of the elementScores array. |
>>> import clusim.sim as sim
>>> from clusim.clustering import Clustering
>>> clustering1 = Clustering(elm2clu_dict={0:[0], 1:[0], 2:[0,1],
3:[1], 4:[2], 5:[2]})
>>> clustering2 = Clustering(elm2clu_dict={0:[0,2], 1:[0], 2:[0,1],
3:[1], 4:[2], 5:[1,2]})
>>> elementScores, relabeled_elements = sim.element_sim_elseq(clustering1,
clustering2,
alpha = 0.9)
>>> print(elementScores)
clusim.clusimelement.
cL1
(x, y, alpha)¶The normalized similarity value based on the L1 probabilty metric corrected for the guaranteed overlap in probability between the two vectors, alpha.
See [GWHA18] for a detailed explaination of the need to correct the L1 metric.
| Parameters: |
|
|---|---|
| Returns: | The 1d numpy array of L1 similarities between the affinity matrices x and y |
clusim.clusimelement.
make_affinity_matrix
(clustering, alpha=0.9, r=1.0, rescale_path_type='max', relabeled_elements=None)¶The element-centric clustering similarity affinity matrix for a clustering. This function automatically determines the most efficient method to calculate the affinity matrix.
See [GWHA18] for a detailed explaination of the affinity matrix.
| Parameters: |
|
|---|---|
| Returns: | The element-centric affinity representation of the clustering as a 2d numpy array |
>>> import clusim.sim as sim
>>> from clusim.clustering import Clustering
>>> clustering1 = Clustering(elm2clu_dict={0:[0], 1:[0], 2:[1], 3:[1],
4:[2], 5:[2]})
>>> pprmatrix = sim.make_affinity_matrix(clustering1, alpha=0.9)
>>> print(pprmatrix)
>>> clustering2 = Clustering(elm2clu_dict={0:[0], 1:[0], 2:[0,1], 3:[1],
4:[2], 5:[2]})
>>> pprmatrix2 = sim.make_affinity_matrix(clustering2, alpha=0.9)
>>> print(pprmatrix2)
clusim.clusimelement.
ppr_partition
(clustering, alpha=0.9, relabeled_elements=None)¶The element-centric clustering similarity affinity matrix for a partition found analytically.
| Parameters: |
|
|---|---|
| Returns: | 2d numpy array The element-centric affinity representation of the clustering |
>>> import clusim.sim as sim
>>> from clusim.clustering import Clustering
>>> elm2clu_dict = {0:[0], 1:[0], 2:[1], 3:[1], 4:[2], 5:[2]}
>>> clustering1 = Clustering(elm2clu_dict=elm2clu_dict)
>>> pprmatrix = sim.ppr_partition(clustering1, alpha=0.9)
>>> print(pprmatrix)
clusim.clusimelement.
make_cielg
(clustering, r=1.0, rescale_path_type='max', relabeled_elements=None)¶Create the cluster-induced element graph for a Clustering.
| Parameters: |
|
|---|---|
| Returns: | The cluster-induced element graph for a Clustering as an igraph.WeightedGraph |
>>> import clusim.sim as sim
>>> from clusim.clustering import Clustering
>>> elm2clu_dict = {0:[0], 1:[0], 2:[1], 3:[1], 4:[2], 5:[2]}
>>> clustering1 = Clustering(elm2clu_dict=elm2clu_dict)
>>> pprmatrix = sim.make_cielg(clustering1, r = 1.0)
>>> print(pprmatrix)
clusim.clusimelement.
find_groups_in_cluster
(clustervs, elementgroupList)¶A utility function to find vertices with the same cluster memberships.
| Parameters: |
|
|---|---|
| Returns: | a list-of-lists containing the groupings of the vertices |
clusim.clusimelement.
numerical_ppr_scores
(cielg, clustering, alpha=0.9, relabeled_elements=None)¶The element-centric clustering similarity affinity matrix for a partition.
| Parameters: |
|
|---|---|
| Returns: | 2d numpy array The element-centric affinity representation of the clustering |
clusim.dag.
DAG
(incoming_graph_data=None, **attr)¶clusim.dag.
Dendrogram
(incoming_graph_data=None, **attr)¶| [ABL10] | Yong-Yeol Ahn, James P Bagrow, and Sune Lehmann. Link communities reveal multiscale complexity in networks. Nature, 466(7307):761–764, June 2010. |
| [CD88] | Linda M. Collins and Clyde W. Dent. Omega: a general formulation of the rand index of cluster recovery suitable for non-disjoint solutions. Multivariate Behavioral Research, 23(2):231–242, 1988. |
| [DDiazGDA05] | Leon Danon, Albert D ıaz-Guilera, Jordi Duch, and Alex Arenas. Comparing community structure identification. Journal of Statistical Mechanics: Theory and Experiment, 2005(09):P09008–P09008, September 2005. |
| [FM83] | Edward B. Fowlkes and Colin L. Mallows. A method for comparing two hierarchical clusterings. Journal of the American Statistical Association, 78(383):553–569, 1983. |
| [GA17] | (1, 2, 3, 4, 5) Alexander J. Gates and Yong-Yeol Ahn. The impact of random models on clustering similarity. Journal of Machine Learning Research, 18(87):1–28, 2017. |
| [GWHA18] | (1, 2, 3, 4) Alexander J. Gates, Ian B. Wood, William P. Hetrick, and Yong-Yeol Ahn. On comparing clusterings: an element-centric framework unifies overlaps and hierarchy. arxiv, pages 1706.06136, 2018. |
| [HA85] | (1, 2) Lawrence Hubert and Phipps Arabie. Comparing partitions. Journal of Classification, 2(1):193–218, December 1985. |
| [Jac12] | Paul Jaccard. The distribution of the flora in the alpine zone. New Phytologist, 11(2):37–50, 1912. |
| [LFK09] | Andrea Lancichinetti, Santo Fortunato, and János Kertész. Detecting the overlapping and hierarchical community structure in complex networks. New Journal of Physics, 11(3):033015, 3 2009. |
| [Mei03] | Marina Meilă. Comparing clusterings by the variation of information. In Learning Theory and Kernel Machines, pages 173–187. Springer, 2003. |
| [NYP12] | Tamás Nepusz, Haiyuan Yu, and Alberto Paccanaro. Detecting overlapping protein complexes in protein-protein interaction networks. Nature Methods, 9(5):471–472, 2012. |
| [Ran71] | William M Rand. Objective Criteria for the Evaluation of Clustering Methods. Journal of the American Statistical Association, 66(336):846, 1971. |


Man convicted of murdering Steven Donaldson found dead in his prison cell
Steven Dickie was sentenced to a minimum of 23 years behind bars for his part in the murder of the 27-year-old last year.
by Daniel Morrow, https://www.dailyrecord.co.uk/authors/daniel-morrow/A man who was convicted of killing Steven Donaldson has been found dead in his cell, according to reports.
Steven Dickie was sentenced to a minimum of 23 years behind bars for his part in the murder of the 27-year-old last year.
Prison officers discovered Dickie’s body at HMP Perth on Friday morning, according to the Evening Telegraph.
The Scottish Prison Service have been approached for comment.
Donaldson’s body was found battered and burned beside the charred shell of his BMW at Kirriemuir’s Loch of Kinnordy Nature Reserve in June 2018.
An autopsy revealed that he had been stabbed, struck with a baseball bat and had his spine severed by a sword or machete.
The Daily Record previously reported that Dickie, along with Callum Davidson and Tasmin Glass would be appealing their sentences for their part in the death of Donaldson.


Search Inside Yourself (chapter 8)
I have been fortunate to have experienced compassionate leadership from both direct managers and non-formal mentors or senior members of my teams over the years. In particular, I've felt this when juggling family and work committments. This genuine compassion, flexibility and interest meant that I was also more invested and productive.
On the flip side to this, I have also experienced not so compassionate leadership or where the compassion / interest has not felt authentic. This impact can be felt even when the leadership is quite removed (i.e. senior leadership). It has resulted in low team morale, average productivity and not feeling like my input adds any real value.
This meditation did't leave me with any particular feeling (i.e. extra positivity or happy glow). By default, I like to see the best in people and their motivations, so can see the benefit of making a habit of this and turning it into more of a conscious thought re: both seeing and giving goodness.
Breathing in the challenge / pain was easy, but breathing it out and away I found quite difficult. I've been practicing a similar exercise for a little while (only when breathing out, focus on letting it go). I'll keep practicing this one and instead try to transform it into a positive intention when breathing out.
This model is around the drivers behind social behaviour. In terms of Phase 0 and bootcamp:
For most of my life, I have been quite conflict adverse. However, in recent years I have seen the benefit of having difficult conversations, given the right situation and if this conversation is going to add value. This has largely been down to my kids, who have made me feel less concerned about always keeping the peace and being comfortable with someone disagreeing with me. Sometimes loudly and very close to my face. And in a busy pubic space. Thanks kids.
Preparing and running through the conversation from various angles in my mind helps. And I would generally only have the conversation if there is a purpose or solution. I find that when this is missing, the conversation just goes around and around, leaving the participants feeling quite grim afterwards.


triaing about Amazon Web Service and MXNet SageMaker, KAIST, Daejeon, Republic of Korea.
2018.07.30 ~ 08.02
Sang Woo Kim and Linh Van Ma, graduated students attend a traing about Amazon Web Service and MXNet SageMaker, KAIST, Daejeon, Republic of Korea.


freeze = numpoly.polynomial(freeze)
if freeze.isconstant():
freeze = freeze.tonumpy().astype(bool)
else:
poly, freeze = numpoly.align_exponents(poly, freeze)
freeze = numpy.isin(poly.keys, freeze.keys)
freeze = [name in freeze.names for name in poly.names]
else:
freeze = freeze.tonumpy()
freeze = numpy.asarray(freeze, dtype=bool)
// decompose into frozen and unfrozen part
poly = numpoly.decompose(poly)
unfrozen = poly(**{


Ion Gaztañaga<EMAIL_ADDRESS>vector
vector
vector
vector
I'm sure that many C++ programmers have ever wondered where does good old realloc
fit in C++. And that's a good question. Could we improve std::vector
performance
using memory expansion mechanisms to avoid too many copies? But std::vector
is not the only container that could benefit from some classic strategies memory allocation: What if we
could take advantage of the insertion of multiple elements in std::list
using
a burst allocation mechanism that could amortize costs (mutex locks, searches...) that
can't be amortized when using single node allocation strategies? Some space-saving
strategies also come to mind with node containers: Can we find a mechanism to build a
memory allocator that offers the size-saving benefits of a simple segregated storage
strategy (see Boost.Pool) without suffering
too big node pools when most of nodes have been deallocated?
This article will explain how some classic improvement strategies have been applied to C++ allocators. Many of these mechanism are being used for shared-memory allocators and containers (see Boost.Interprocess) where size restrictions are tighter than with heap allocators and other strategies (e.g. per-thread-pthread pools) are not applicable. So we'll be using Boost.Interprocess containers to measure the speed up that we can obtain when using those classic strategies in C++.
Obviously, these C++ allocators need some underlying general purpose allocator, since new and delete don't offer expansion and burst capabilities. In this article we'll use a modified Doug Lea Malloc, aka DLmalloc memory allocator with new basic functions that will offer the necessary underlying machinery to implement all these classic strategies. DLmalloc is known to be very size and speed efficient, and this allocator is used as the basis of many malloc implementations, including multithreaded allocators built above DLmalloc (See ptmalloc2, ptmalloc3 or nedmalloc ). So improvements obtained by the classic strategies applied to C++ will measure real-world speedups, even when the allocator is very efficient.
I've developed some additional classes, like STL allocators, pools and tests, I've put all this code under Boost Software license, and I've respected Boost guidelines so that the developed code can be considered integrated in the Boost Container..
vector
There've been a couple of C++ proposal to add in-place expansion mechanisms to standard allocators (N1953: Upgrading the Interface of Allocators using API Versioning written by Howard Hinnant and N2045: Improving STL allocators written by me based on Hinnant's proposal). Unfortunately they didn't receive much interest in the committee but there is hope that we could get some of this functionality for C++1x if the C++ community shows some interest. Let's review a bit what these proposals said:
Hinnant's proposal adds some new functionalities to C++ allocators:
The first functionality is interesting to avoid wasting some precious bytes the memory
allocator adds in the end of the buffer due to alignment reasons or because its own
memory allocation algorithm. As an example, DLmalloc on 32 bit systems will need a
minimum of 16 bytes for every allocation (4 bytes are payload and 12 bytes are available
for the user): If we try to initialize std::string
with a 4 character
narrow string ("abcd"
) we will waste 8 bytes, because we have no way to know
that there is room in our newly allocated buffer that could be used for longer strings
without going again through the allocator. Other allocators waste even
more memory. In 64 bit systems the minimum size (and thus, the waste) is bigger:
32 bytes (24 bytes available for the user) for DLmalloc.
The second functionality is the classical use case of realloc in C: instead of
allocating a new buffer, the programmer tries to expand the current one. If the
expansion succeeds, there is no need to copy data to the new buffer (in C++, that means
avoiding potentially costly copy-constructors). The third one is exactly the inverse: a
vector that has grown considerably has now a few elements, vector.capacity()
is
much bigger than vector.size()
and we'd like to return memory
to the system. Many programmers use the
shrink-to-fit trick to return memory to the system, but this trick needs
a possibly throwing copy, whereas a shrink to fit operation implemented
by the allocator would not need any copying at all.
The last functionality is really interesting because a vector increases its capacity
usually using a growth factor (usually 1.5f or 2.0f) to avoid too many reallocations. That is, when we insert
new objects in a vector and vector.capacity() == vector.size()
, then the
vector allocates much more memory than the size needed to insert a new object. When
allocating new memory to insert a new object, limit size is size() + 1
,
preferred size is size()*growth_factor
and received size is the real
size of the buffer. When inserting a new element in a vector, is usually better to
expand the memory to hold the new element than to allocate a new bigger buffer.
N2045 makes some additions:
operator new
and operator
new[]
.
The first addition is useful for embedded systems and other size-limited memories, like fixed-size shared memory. If a vector can only be expanded forward, then it can't reuse preceding free memory if that preceding memory is not big enough (that is, 1.5 or 2.0 times bigger than the current buffer). With backwards expansion, this limitation disappears and backwards expansion can be combined with forward expansion to optimize memory usage.
The vector has to copy elements backwards so backwards expansion needs exactly the same number of copies as a new allocation. Many times backwards expansion can be implemented very efficiently in some memory algorithms that have fast access to previous and next memory buffers. Backwards expansion also has some downsides:
sizeof(Type)
== 12 can't be expanded backwards 16 bytes, because the
distance between the old beginning and the new beginning is not multiple of 12, and thus, the
old object will be partially overwritten and it can't be safely move-assigned.The second addition tries to compact in a single call several tries to expand or allocate memory because usually a vector will first try to expand memory and if this fails, it will try to allocate a new buffer. Since checking for expansion capabilities is quite fast comparing to mutex locking and other checks performed by the allocator, both functions can be combined in a single call.
The third addition (separating node and array allocation) is based on the fact that with
the addition of expansion functions, node allocators based classic segregated storage
pools won't be able to be allocators with expansion capabilities. This might not sound
like a big problem for pure-node containers like std::list
but some hybrid
containers like std::unordered_map
wouldn't be able to use both segregated
storage (for nodes) and expansion features (for the bucket array).
Furthermore, some allocators (see N2554 The Scoped Allocator Model (Rev 2)) can be propagated through containers, so having an allocator that can use in-place expansion capabilities and node-pooling capabilities is very interesting. And this can only be achieved if the allocator uses different functions for single element and array operations.
The last two additions are just optimizations to reduce locking and to minimize the number of allocation calls.
Hinnant's proposal was implemented in the Freescale (then Metrowerks) standard library (MSL) with great success. My approach was implemented in Boost.Interprocess. This article is an evolution of my last proposal but applying these techniques in a widely used heap allocator.
allocation_command
. This is the
explanation of the function:
enum allocation_type {//Bitwise OR (|) combinable values allocate_new = ..., expand_fwd = ..., expand_bwd = ..., shrink_in_place = ..., try_shrink_in_place = ..., nothrow_allocation = ... }; template<class T> std::pair<T *, bool> allocation_command ( allocation_type command, std::size_t limit_size , std::size_t preferred_size, std::size_t &received_size, T *reuse_ptr = 0);
Preconditions for this function:
command
must contain at least of these values: shrink_in_place
,
try_shrink_in_place
, try_shrink_in_place
, expand_fwd
, expand_bwd
or allocate_new
.
command
contains the value shrink_in_place
it can't
contain any of these values: expand_fwd
, expand_bwd
,
allocate_new
, try_shrink_in_place
.
command
contains the value try_shrink_in_place
it can't
contain any of these values: expand_fwd
, expand_bwd
,
allocate_new
, shrink_in_place
.
command
contains expand_fwd
or expand_bwd
, the
parameter reuse_ptr
must be non-null and returned by a previous allocation function.
command
contains the value shrink_in_place
,
the parameter limit_size
must be equal or greater than the parameter preferred_size
.
command
contains any of these values: expand_fwd
or
expand_bwd
, the parameter limit_size
must be equal or less than the
parameter preferred_size
.Which are the effects of this function:
command
contains the value shrink_in_place
,
(with optional additional nothrow_allocation
) the function will
try to reduce the size of the memory block referenced by pointer reuse_ptr
to the
value preferred_size
moving only the end of the block. If it's not possible, it
will try to reduce the size of the memory block as much as possible as long as this results in
size(p) <= limit_size
. Success is reported only if this results in preferred_size
<= size(p)
and size(p) <= limit_size
.
command
contains the value try_shrink_in_place
,
(with optional additional nothrow_allocation
) the function will act as if
a shrink_in_place
was demaned but it won't shrink the buffer. This function
is useful to know if a shrink operation will have success with the given parameters and
obtain in the parameter received_size
a value that is guaranteed to succeed
as limit_size
on a subsequent shrink in place operation. This function is
useful to know exactly how many objects a caller should destroy with the given
limit_size
and preferred_size
.
command
only contains the value expand_fwd
(with
optional additional nothrow_allocation
), the allocator will try to increase the
size of the memory block referenced by pointer reuse moving only the end of the block to the
value preferred_size
. If it's not possible, it will try to increase the size of
the memory block as much as possible as long as this results in size(p) >= limit_size
.
Success is reported only if this results in limit_size <= size(p)
.
command
only contains the value expand_bwd
(with
optional additional nothrow_allocation
), the allocator will try to increase the
size of the memory block referenced by pointer reuse_ptr
only moving the start of
the block to a returned new position new_ptr
. If it's not possible, it will try
to move the start of the block as much as possible as long as this results in size(new_ptr)
>= limit_size
. Success is reported only if this results in limit_size <=
size(new_ptr)
.
command
only contains the value allocate_new
(with
optional additional nothrow_allocation
), the allocator will try to allocate
memory for preferred_size
objects. If it's not possible it will try to allocate
memory for at least limit_size
objects.
command
only contains a combination of expand_fwd
and
allocate_new
, (with optional additional nothrow_allocation
) the
allocator will try first the forward expansion. If this fails, it would try a new
allocation.
command
only contains a combination of expand_bwd
and
allocate_new
(with optional additional nothrow_allocation
), the
allocator will try first to obtain preferred_size
objects using both methods if
necessary. If this fails, it will try to obtain limit_size
objects using both methods if necessary.
command
only contains a combination of expand_fwd
and
expand_bwd
(with optional additional nothrow_allocation
), the
allocator will try first forward expansion. If this fails it will try to obtain preferred_size
objects using backwards expansion or a combination of forward and backwards expansion. If this
fails, it will try to obtain limit_size
objects using both methods if necessary.
command
only contains a combination of allocation_new, expand_fwd
and expand_bwd
, (with optional additional nothrow_allocation
) the
allocator will try first forward expansion. If this fails it will try to obtain preferred_size
objects using new allocation, backwards expansion or a combination of forward and backwards
expansion. If this fails, it will try to obtain limit_size
objects using the same methods.
received_size
.
On failure the allocator writes in received_size
a possibly successful limit_size
parameter for a new call.Throws an exception if two conditions are met:
nothrow_allocation
.This function returns:
nothrow_allocation
the first member will be 0 if the allocation/expansion fails or there is an error in
preconditions.
Notes:
char
as template argument the returned buffer will be suitably aligned to hold any type.
char
as template argument and a backwards expansion is
performed, although properly aligned, the returned buffer might not be suitable because the
distance between the new beginning and the old beginning might not multiple of the type the
user wants to construct, since due to internal restrictions the expansion can be slightly
bigger than the requested bytes. When performing backwards expansion, if you have already
constructed objects in the old buffer, it's important to correctly specify the type.Obviously, we need an underlying C function that offers these possibilities. I've added the following function to the modified dlmalloc library:
typedef struct boost_cont_command_ret_impl { void *first; int second; }boost_cont_command_ret_t; boost_cont_command_ret_t boost_cont_allocation_command ( allocation_type command , size_t sizeof_object , size_t limit_objects , size_t preferred_objects , size_t *received_objects , void *reuse_ptr );
This function does the same job as allocation_command
, so it takes the
same options and an additional parameter indicating the size of the object (specially
important for backwards expansion). This function does not throw exceptions because C
has no exceptions but other than these two issues, its use is exactly the same
as allocation_command
.
To compare apples to apples, we just can't compare the standard allocator versus an
allocator based on DLmalloc with expansion capabilities. For this purpose we develop an
allocator (called, surprisingly, ba::allocator
). Here's the declaration:
namespace boost { namespace container { template<class T, unsigned Version = 2, unsigned int AllocationDisableMask = 0> class allocator; }//namespace container { }//namespace boost {
The first template parameter is the type of the objects to be allocated. The second is
the version of the allocator (see
N1953) for details. If Version is 1, then the allocator is a standard conforming
classic allocator around dlmalloc
and dlfree
with no
additional features. If Version is 2, then the allocator has expansion capabilities and
other features like specifying limit and preferred sizes and obtaining the real size of
an allocated memory, separated node and array allocations, etc...
The third parameter is a mask that can be used to disable some capabilities. For
example, specifying expand_bwd | expand_fwd
will disable forward
and backwards expansion and the allocator will only provide new buffer allocations.
vector
Let's first present the class that will be used in our performance tests. It's a simple
wrapper over an int
, with a copy constructor that realizes a job that will
be equivalent to most move-constructors in C++0x. Of course performance gains will be
bigger in copyable but non-moveable heavy objects, but I think this class is fair
enough.
class MyInt { int int_; public: MyInt(int i = 0) : int_(i){} MyInt(const MyInt &other) : int_(other.int_) {} MyInt & operator=(const MyInt &other) { int_ = other.int_; return *this; } };
Now we'll push back an element one by one in a vector, and measure the time using Boost.DateTime:
unsigned int numalloc = 0, numexpand = 0, capacity = 0; ptime tini = microsec_clock::universal_time(); for(unsigned int r = 0; r != num_iterations; ++r){ bi::vector<MyInt, IntAllocator> v; v.reset_alloc_stats();//Reset allocation statistics for(unsigned int e = 0; e != num_elements; ++e) v.push_back(e); numalloc += v.num_alloc; numexpand += v.num_expand_fwd; capacity = static_cast<unsigned int>(v.capacity()); } ptime tend = microsec_clock::universal_time();//...
We'll test 4 different allocators:
std::allocator<int>
, the standard
allocator that comes with the C++ compilerba::allocator<int, 1>
, a STL
conformant allocator around dlmalloc
and dlfree
.ba::allocator<int, 2, expand_bwd |
expand_fwd>
, an allocator with capabilities to specify a limit size the
preferred size and real size of a buffer, but with expansion capabilities disabled.ba::allocator<int, 2>
, a fully
equipped improved allocator. (Note: There is no need to disable backwards expansions because
forward expansion has always preference over new allocations and backwards expansion).
and we'll use several [num_iterations, num_elements]
combinations: [10000,
10000], [100000, 1000], [1000000, 100] and [10000000, 10]
For each allocator we'll show the following information:
push_back
speed (normalized to AllocatorPlusV1)
As we see in the picture, DLmalloc is faster than the standard allocator
provided by MSVC 7.1 (StdAllocator vs. AllocatorPlus). We also see that
V2 allocators call less times to allocator functions (for size=10, 4 times vs. 6 times),
because using the received_size parameter of allocation_command
the
container can take advantage of the real size of the newly allocated small buffer.
For big sizes (size=10000), due to the expansion capabilities of AllocatorPlusV2, this is twice as fast as AllocatorPlusV2Mask and 2.5 times faster than the standard conforming, DLmalloc based AllocatorPlusV1. As we can see in the third graph, only AllocatorPlusV2 performs expand in place, whereas the rest only allocate new buffers.
Now we'll execute the same test in a Linux (Suse 10.1) virtual machine (VMWare 6) using gcc-4.1 compiler
and will check push_back
times:
We see that the standard allocator is faster than our V1 (a standard conforming DLmalloc wrapper) by a small margin for some sizes and slightly slower for bigger sizes. That's because gblic malloc is based on ptmalloc2, which is actually based on DLmalloc, but uses per-thread-pools, so minimizes mutex locks.
Like in Windows, expand-in-place capable allocator is twice as fast as the V1 allocator, confirming that forward expansion offers a considerable speed up. This speed up will be noticeable in initialization phases when vectors are filled with many back insertions. The speed-up will be more noticeable if vector elements are elements with no move constructors (e.g. third-party classes than can't be updated with move semantics).
vector
Historically backwards expansion has not been very used for allocation strategies, basically because it does not offer the speed improvements offered by forward expansion for usual vector implementations. Similarly to new allocation, we need to move old objects (an implementation might avoid data-moving if it manages uninitialized data in the beginning of the memory buffer, but that's not usual). Backwards expansion has the ability to reduce the peak memory used by the vector (while allocating new memory, the vector has to maintain the old buffer until copies data to the new one) effectively reusing free memory placed just before the buffer to be expanded.
As we've said before, the backwards expansion algorithm has to calculate the LCM (least common multiple) of the memory allocation alignment (8 bytes in DLmalloc) and the size of the object. For very efficient algorithms like DLmalloc, I've found that calculating the LCM using the traditional Euclidean algorithm was a big overhead that made backwards expansion considerably slower than new allocation. It's necessary to take advantage of the power of 2 memory alignment and implement optimizations for object sizes also power of 2 or multiple of 2, 4, or 8 bytes, and use optimized versions to calculate the LCM. Fortunately, these optimizations made backwards expansion slightly faster than a new allocation, making backwards expansion better than new allocation in every aspect.
To test backwards expansion we'll execute the same push_back
test
using the following 4 allocators:
std::allocator<int>
, the standard
allocator that comes with the C++ compiler
ba::allocator<int, 1>
, a STL
conformant allocator around dlmalloc
and dlfree
.
ba::allocator<int, 2, expand_bwd |
expand_fwd>
, an allocator with capabilities to specify a limit size the
preferred size and real size of a buffer, but with expansion capabilities disabled.
ba::allocator<int, 2, expand_fwd>
,
a fully equipped improved allocator, that avoids forward expansion (forward expansion
has priority over backwards expansion, so we need to disable it to only measure backwards
expansion).And now in a Linux (Suse 10.1) virtual machine (VMWare 6) using gcc-4.1 compiler:
We see that for most cases backwards expansion (AllocatorPlusV2) is slightly faster than new
allocation (AllocatorPlusV1) and new allocation with received_size
capabilities
(AllocatorPlusV2Mask).
vector
The
Shrink-to-fit is a widely used idiom that can be improved with the shrink_in_place"
option provided by allocation_command
method. To test this function we'll use the following test:
const std::size_t Step = 5; ptime tini = microsec_clock::universal_time(); typedef boost::interprocess::detail::integral_constant <unsigned, boost::interprocess::detail::version<Allocator>::value> alloc_version; for(unsigned int r = 0; r != num_iterations; ++r){//Create a vector with num_elements size bi::vector<MyInt, IntAllocator> v(num_elements); v.reset_alloc_stats();//Empty the vector erasing the last Step elements and calling shrink_to_fit() for(unsigned int e = num_elements; e != 0; e -= Step){ v.erase(v.end() - Step, v.end()); v.shrink_to_fit(); } } ptime tend = microsec_clock::universal_time();
That is, we'll initialize the vector with an initial size and will erase the last Step elements (5 in this case),
and shrink to fit the capacity of the vector. We'll repeat this operation for different
[num_iterations, num_elements]
combinations: [100,
10000], [1000, 200] and [10000, 500]
To test shrink to fit we'll execute the test using the following 3 allocators:
std::allocator<int>
, the standard
allocator that comes with the C++ compiler
ba::allocator<int, 1>
, a STL
conformant allocator around dlmalloc
and dlfree
.
ba::allocator<int, 2, expand_fwd>
,
a fully equipped improved allocator with shrink to fit capacity.
As the initial vector size grows, AllocatorPlusV2
shines (up to 90 times faster!)
because a shrink to fit operation is a no-throw
operation that can have amortized constant-time complexity due to the fact that an allocator usually implements
shrink to fit with a deallocation: the allocator divides the old buffer in two independent buffers and
deallocates the second buffer. On the other hand, vectors with allocators with no shrink to fit functionality
need to allocate a new buffer, move elements to the new one (moving elements is a linear operation
with the size of the vector) and deallocate the old buffer.
Now we'll execute the same test in a Linux (Suse 10.1) virtual machine (VMWare 6) using gcc-4.1 compiler
and will check push_back
times:
Result are similar to Windows results, with AllocatorPlusV2
shinning more and more when initial vector
size grows.
Many times, operations can be performed faster if they are packed in groups, because some
costs are not related to the number of operations, but to the number of groups. An example
of this operations is the template
operation in vectors. If Iterator
is a forward iterator, most implementations
calculate the distance between begin
and end
so that they know
the size of the buffer needed to hold all those elements. With this information, they only
perform one allocation to insert all the range.
Other containers can't take advantage of this possibility because they are node containers, meaning that each element is obtained with a call to the allocator that allocates a single element. Since each element has its own independent memory, these containers offer stronger iterator validity guarantees and pointers and references to inserted objects are not easily invalidated. On the other hand, inserting N elements in those containers, require N calls to the allocator.
To solve this, the idea is to have a function that could allocate a lot of objects in a single call, guaranteeing that each object can be individually deallocatable. Some memory management algorithms offer this possibility, even with the possibility to specify a different buffer size for each operation in a group. For example, DLmalloc offers the following two functions:
void** independent_calloc(size_t n_elements, size_t element_size, void*chunks[]);
Explanation: independent_calloc
is similar to calloc, but instead of returning a
single cleared space, it returns an array of pointers to n_elements
independent elements that can hold contents of size elem_size, each
of which starts out cleared, and can be independently freed,
realloc'ed etc. The elements are guaranteed to be adjacently
allocated (this is not guaranteed to occur with multiple callocs or
mallocs), which may also improve cache locality in some
applications. [...]
void** independent_comalloc(size_t n_elements, size_t sizes[], void* chunks[]);
Explanation: independent_comalloc
allocates, all at once, a set of n_elements
chunks with sizes indicated in the "sizes" array. It returns an array of pointers to these elements,
each of which can be independently freed, realloc'ed etc. The elements are guaranteed to be
adjacently allocated (this is not guaranteed to occur with multiple callocs or mallocs),
which may also improve cache locality in some applications. [...]
For these two functions each element must be individually freed when it is no longer needed and objects are guaranteed to be contiguously allocated (to help cache locality). Also, the "chunks" argument is optional (i.e., may be null, which is probably the most typical usage). If it is null, the returned array is itself dynamically allocated and should also be freed when it is no longer needed. Otherwise, the chunks array must be of at least n_elements in length. It is filled in with the pointers to the chunks.
According to DLmalloc documentation independent_calloc
simplifies and speeds up implementations of many
kinds of pools. It may also be useful when constructing large data
structures that initially have a fixed number of fixed-sized nodes,
but the number is not known at compile time, and some of the nodes
may later need to be freed:
struct Node { int item; struct Node* next; }; struct Node* build_list() { struct Node** pool; int n = read_number_of_nodes_needed(); if (n <= 0) return 0; pool = (struct Node**)(independent_calloc(n, sizeof(struct Node), 0); if (pool == 0) die();// organize into a linked list... struct Node* first = pool[0]; for (i = 0; i < n-1; ++i) pool[i]->next = pool[i+1]; free(pool);// Can now free the array (or not, if it is needed later) return first; }
According to DLmalloc documentation independent_comalloc
can be used to speed up allocation in cases where several structs or
objects must always be allocated at the same time:
struct Head { ... } struct Foot { ... } void send_message(char* msg) { int msglen = strlen(msg); size_t sizes[3] = { sizeof(struct Head), msglen, sizeof(struct Foot) }; void* chunks[3]; if (independent_comalloc(3, sizes, chunks) == 0) die(); struct Head* head = (struct Head*)(chunks[0]); char* body = (char*)(chunks[1]); struct Foot* foot = (struct Foot*)(chunks[2]);// ... }
Unfortunately, these two functions have some downsides when working with some containers:
list
is forced to allocate an
array to hold pointers to these nodes) and imposes an unnecessary overhead to node containers.The first issue (the required external or internally allocated array) can be avoided if every memory node is linked with an intrusive singly linked list and offering an iterator-like interface. The intrusive list is built in the first bytes reserved for the user data because the minimum node size guarantees 12 bytes for 32 bits systems and 24 bytes for 64 bit systems. Obviously, once the user has overwritten that memory, there is no way to iterate to the next node so the programmer must be careful. Let's present these new functions:
These functions offer an emulation of a C++ input iterator./* Iterator functions */ typedef /**/ multialloc_it_t;/* Iterator type */ BOOST_CONTAINER_INIT_END_IT(IT)/* Postcondition: BOOST_CONTAINER_IS_END_IT(IT) != 0 */ BOOST_CONTAINER_IS_END_IT(IT)/* Is an end iterator? */ BOOST_CONTAINER_NEXT_IT(IT)/* operator ++ emulation */ BOOST_CONTAINER_ADDR_IT(IT)/* operator* emulation, returns the address of the memory */
These functions offer the possibility of building an intrusive chain (list) of nodes previously allocated by DLmalloc and obtain an iterator that can traverse them. These functions are used to build a range that can be deleted in a single call using with/* Multiallocation chain functions */ typedef /**/ multialloc_it_chain_t;/* Chain type */ BOOST_CONTAINER_IT_CHAIN_INIT(CHAIN)/* Postcondition: BOOST_CONTAINER_IT_CHAIN_IT(IT_CHAIN) is end it */ BOOST_CONTAINER_IT_CHAIN_PUSH_BACK(CHAIN, MEM)/* Push back the node MEM in the intrusive linked list chain */ BOOST_CONTAINER_IT_CHAIN_PUSH_FRONT(CHAIN, MEM)/* Push front the node MEM in the intrusive linked list chain */ BOOST_CONTAINER_IT_CHAIN_SPLICE_BACK(CHAIN, CHAIN2)/* Splice chain2 in the end of the first chain */ BOOST_CONTAINER_IT_CHAIN_IT(IT_CHAIN)/* Return an input iterator that traverse the chain */ BOOST_CONTAINER_IT_CHAIN_SIZE(IT_CHAIN)/* Returns the size of the chain */
boost_cont_multidealloc()
(See below).
/* Some defines for "contiguous_elements" parameters */ DL_MULTIALLOC_ALL_CONTIGUOUS/* Allocate all elements contiguous on memory */ DL_MULTIALLOC_DEFAULT_CONTIGUOUS/* The implementation chooses the maximum contiguous elements /* Burst allocation: Allocates "n_elements nodes" of size "elem_size" with a maximum (if possible) of "contiguous_elements". On success returns an input iterator. On failure returns an "end" iterator.*/ multialloc_it_t boost_cont_multialloc_nodes (size_t n_elements, size_t elem_size, size_t contiguous_elements);/* Burst allocation: Allocates "n_arrays" of elements, whose size is "sizeof_element" and whose lengths are specified in the "sizes" parameter. Contiguous memory won't be (if possible) bigger than "contiguous_elements"*sizeof_element. On success returns an input iterator. On failure returns an "end" iterator.*/ multialloc_it_t boost_cont_multialloc_arrays (size_t n_arrays, const size_t *lengths, size_t sizeof_element, size_t contiguous_elements);/* Burst deallocation: deallocates all the range specified by the iterator */ void boost_cont_multidealloc(multialloc_it_t it);
boost_cont_multialloc_nodes
is a function that allocates multiple nodes of the same size in the same call returning
an iterator to the range. is a function that allocates multiple arrays in the same call returning
an iterator to the range. The user can specify the (suggested) contiguous number of elements in both functions.
boost_cont_multidealloc
deallocates a range of arrays or nodes that have been allocated
by boost_cont_multialloc_nodes
, boost_cont_multialloc_arrays
or allocated by other DLmalloc functions and
chained using BOOST_CONTAINER_IT_CHAIN_XXX
functions.
Now that we have a low-level swiss knife we can define a C++ interface for burst allocation:
template<class T> class allocator {Burst allocation also follows the separation between node (size == 1) and array allocation functions so that node allocation can use segregated storage mechanisms, whereas array allocation can use another approach that can be used with expansion functions (//... typedef /**/ multiallocation_iterator;//wrapper over multialloc_it_t typedef /**/ multiallocation_chain;//wrapper over multialloc_chain_t //------------------------------------------------------------------ // Functions for array allocation (expandable memory) //------------------------------------------------------------------ //Allocates many elements of size elem_size in a contiguous block //of memory. Elements must be individually deallocated with deallocate() multiallocation_iterator allocate_many(size_type elem_size, size_type n_elements);//Allocates n_elements elements, each one of size elem_sizes[i] //Elements must be individually deallocated with deallocate() multiallocation_iterator allocate_many(const size_type *elem_sizes, size_type n_elements);//Deallocates the memory arrays pointed by the iterator range starting at it void deallocate_many(multiallocation_iterator it);//------------------------------------------------------------------ //Functions for node (size == 1, non-expandable memory) allocation //------------------------------------------------------------------ //Allocates many elements of size == 1. //Elements must be individually deallocated with deallocate_one() multiallocation_iterator allocate_individual(size_type num_elements);//Deallocates the memory nodes pointed by the iterator range starting at it void deallocate_individual(multiallocation_iterator it); };
allocation_command
).
We have all that we need to implement burst allocation and deallocation for STL containers. Now, let's measure if this leads to any speed improvement.
A good place to take advantage of burst allocation is range insertion. Other operations(range assignment, copy construction) are also good places to implement burst allocation. So let's try this code with several allocators to test insertion time:
tini = microsec_clock::universal_time(); bi::list<MyInt, IntAllocator> l; for(unsigned int r = 0; r != num_iterations; ++r){ l.insert(l.end(), num_elements, MyInt(r)); } tend = microsec_clock::universal_time();
That is, we'll try insertions of different range sizes (num_elements
) and different
iterations (num_iterations
). We'll end up with the same number of elements in the
list, so we can compare results easier. To measure burst deallocation we'll preprocess several
iterator ranges and measure the time to completely empty the list:
//Now preprocess ranges to erase std::vector <typename bi::list<MyInt, IntAllocator>::iterator> ranges_to_erase; ranges_to_erase.push_back(l.begin()); for(unsigned int r = 0; r != num_iterations; ++r){ typename bi::list<MyInt, IntAllocator>::iterator next_pos(ranges_to_erase[r]); std::size_t n = num_elements; while(n--){ ++next_pos; } ranges_to_erase.push_back(next_pos); }//Measure range erasure function tini = microsec_clock::universal_time(); for(unsigned int r = 0; r != num_iterations; ++r){ l.erase(ranges_to_erase[r], ranges_to_erase[r+1]); } tend = microsec_clock::universal_time();
As shown, a good place to take advantage of burst allocation is range erasure along with clear()
and destructors.
We'll test 3 different allocators:
std::allocator<int>
, the standard
allocator that comes with the C++ compilerba::allocator<int, 1>
, a STL
conformant allocator around dlmalloc
and dlfree
(no burst allocation).ba::allocator<int, 2>
, burst-allocation capable
allocator.[num_iterations, num_elements]
combinations: [200,
10000], [2000, 1000], [20000, 100] and [200000, 10]
For each allocator we'll show the following information:
The graph shows that allocation speed per element is constant for AllocatorPlusV1 (surprisingly, not so constant for
Visual's standard allocator) and this is pretty logical since each element needs an allocation. AllocatorPlusV2 is
using DL_MULTIALLOC_DEFAULT_CONTIGUOUS
which allocates contiguous nodes up to 4096 bytes. That's why
AllocatorPlusV2 performance stabilizes for big ranges reaching to a 3x speedup.
Burst deallocation improvements are more modest, why?
list
must construct a node chain (iterating through all nodes) before calling
deallocate_individual
. That is, we must traverse nodes twice (once to construct the chain and
another one internally in the internal C function)This means that burst deallocation is just a loop of plain deallocations, amortizing costs like mutex locks, checks, function calls and returns and other common operations. Nevertheless, the test shows a 30% speedup when comparing to node to node deallocation with quite big ranges (>1000) and still noticeable speedups (20%) with small ranges (>=10).
Now we'll execute the same test in a Linux (Suse 10.1) virtual machine (VMWare 6) using gcc-4.1:
In Linux, the standard allocator (ptmalloc2, based on DLmalloc) performs very well, and the lock reduction achieved by its per-thread-pool approach offers a similar performance than burst allocation (AllocatorPlusV2) for small ranges. With bigger ranges (>=100) AllocatorPlusV2 maintains (more or less) its performance while StdAllocator can't keep up. Like in WinXP Visual 7.1 tests, AllocatorPlusV2 is faster (up to 2x in some cases) than AllocatorPlusV1 for big ranges.
Burst deallocation is not faster than the standard allocator in Linux, surely because ptmalloc2 reduces
mutex locks just like burst deallocation, but burst deallocation needs to traverse the range to be
erased twice as explained before. When comparing to AllocatorPlusV1, that is, a wrapper around
dlmalloc
and dlfree
burst deallocation (AllocatorPlusV2) is 30% faster for
big ranges.
When developing allocators to improve node containers performance, one of the widely used approaches is using simple segregated storage (e.g. Boost.Pool). The idea behind simple segregated storage is to divide a big memory portion ("block") allocated through a general purpose memory manager into fixed-size "nodes". A memory manager ("pool") holds a list of "blocks" and a singly linked list of free nodes. Since all nodes are the same size, Simple Segregated Storage can't serve nodes of different sizes. To solve this, an application creates a different pool for each size and usually different types with the same size share the same pool.
The free node list is intrusive (since the node is free, the list pointer is built in the node), so that there is no size overhead for each node. Simple Segregated Storage is very fast:
Now the question is: when does the pool return fully free "blocks" (allocated each time the free node list was empty) to the general purpose memory manager so that they can be reused by other pools or non-pool allocators? The common answer is: usually never. Why? Simple Segregated Storage erases all bookeeping data from the node and this makes "block" deallocation very expensive: the pool needs to traverse the free nodes list (nodes are not ordered by their original block) and check the address of each node against the address of each "block" just to check if all the nodes of a "block" are free and the block can be safely deallocated. If we have B blocks and N nodes, this is a O(N*B) operation. Usually N (and B) can be quite high and this operation can take minutes if the application has allocated several tens of thousands of nodes. That's why the option to trim the memory is provided only as an optional and explicit operation.
A manual operation makes allocator changes non-portable (How is that manual trimming activated? How long does it take?) so many applications just ignore this operation. This also has a drawback: if an application allocates a big amount of nodes in a container and then destroys the container, the pool will hold a big list of free nodes but that memory won't be reused by any other container not using a pool with the same node size, leading to excessive memory waste.
Can we obtain the small size overhead of simple segregated storage and a fast, continuous, memory trimming operation? The idea behind adaptive pools is simple: when deallocating a node, an efficient self-trimming node pool needs a fast access to the "block" containing the node. If so, the pool can check how many free nodes are in that "block" (the "block" has a header storing the number of free blocks) and if all nodes are free, the pool can return that block to the general purpose memory manager.
The problem is that storing bookeeping data (a pointer to the block containing that node) in a node has a size overhead. But there is an extremely fast way to obtain a pointer to the block containing the node with zero size overhead per-node: memory alignment.
Suppose a 4KB "block" also aligned to 4KB: a node just needs a mask operation to obtain the address of the block. Once we have it, we can check the number of free nodes and deallocate the block if all the nodes are free. And once we have fast access to the "block" we can develop a more complicated trimming scheme that favors the creation of free "blocks" and improves trimming probabilities.
Allocators usually have a payload that store bookeeping information for deallocation. If an adaptive pool allocates 4KB bytes aligned to 4KB, it will really allocate 4KB + payload bytes where the start of the non-payload section is aligned to 4KB. This means that the memory adjacent to this aligned block won't be suitable for a new 4KB aligned allocation leading to excessive memory waste (a 4KB allocation would waste next 4KB - payload bytes of memory).
There is a simple solution: allocate (4KB - payload bytes) bytes aligned to 4KB. This simple solution make contiguous memory usable for a future 4KB aligned allocation leading to optimal memory usage. That's why knowing the size of the payload is important for aligned memory allocations where the size of the allocation is not fixed.Once we have access from a node to its block, we can implement different policies for them. Once a block is completely free we can just deallocate it but the allocation pattern could lead to several half-used blocks, increasing in practice the memory usage we'll trying to minimize.
Alternatively, we can implement a strategy in order to minimize the number of in-use blocks. We can try to allocate nodes always from blocks with less free nodes, leading, at least in theory, to more fully used blocks and more fully free blocks that could be deallocated faster. Obviously, this block management must be very fast: searching for the most used block can ruin performance, specially when comparing with the efficient simple segregated storage. The same happens when deallocating a node: if block management needs too many operations deallocation can have very bad performance.
Adaptive pools can require excessive alignment requirements when many nodes are allocated in a chunk. If a block is configured to hold at least 256 nodes and the size of a node is 24 bytes, the required size for the block is (block payload + 20*256) > 4096 -> 8196 bytes, which also needs 8196 bytes alignment. This means that increasing the number of nodes a block can hold also increases the required alignment.
We can improve the excessive alignment if we divide each block in sub-blocks. The first sub-block contains the payload of the block and the rest of sub-blocks just store a pointer to the first sub-block. This leads to an additional degree of freedom: block overhead. The overhead per block (number of nodes * node size)/ (block size) determines the size (and the alignment) of a sub-block, whereas the number of nodes per block determines the number of sub-blocks per block. This trick maintains the alignment requirement lower than the approach that does not use sub-blocks and constant with the number of nodes per block. On the other hand, deallocation requires an additional indirection (from node to subblock and from subblock to the block header) and a bit more complicated block initialization.
adaptive_pool
adaptive_pool
is built above the aligned memory allocation function
from our modified DLmalloc library. Alignment must be power of two:
void* boost_cont_memalign(size_t bytes, size_t alignment);
adaptive_pool
is implemented as follows:
This is the declaration of adaptive_pool
:
const std::size_t ADP_nodes_per_block = unspecified; const std::size_t ADP_max_free_blocks = unspecified const std::size_t ADP_overhead_percent = unspecified; const std::size_t ADP_only_alignment = unspecified; template < class T , unsigned Version = 2 , std::size_t NodesPerBlock = ADP_nodes_per_block , std::size_t MaxFreeBlocks = ADP_max_free_blocks , std::size_t OverheadPercent = ADP_overhead_percent > class adaptive_pool;
Description of the template parameters:
ADP_only_alignment
, then no sub-blocks will be used
and NodesPerBlock will determine the alignment required by blocks.
To allocate a new node adaptive_pool
needs to:
To deallocate a new node adaptive_pool
needs to:
adaptive_pool
In this test we'll measure 8 allocators:
ba::allocator<int, 1>
, a STL
conformant allocator around dlmalloc
and dlfree
(no burst allocation).ba::allocator<int, 2>
, burst-allocation capable
allocator.All pool allocators (allocators 3-8) are configured with a minimum of 256 nodes per block. For a int list, in 32 bit systems, the required alignment is 4096 bytes for 3 and 4 allocators (adaptive pools with no sub-blocks) and 2048 bytes for 5 and 6 allocators (adaptive pools with sub-blocks).
For each allocator we'll show the following information:
The test will be the same as the used in the section Testing burst allocation. Now let's see the results of the test in a Windows XP machine (AMD 1.47 Ghz) using Visual C++ 2003:
In general, insertion speeds are better for pool allocators than for DLmalloc. Analyzing only V1 allocators
(no burst allocation) we can see that SimpleSegregatedStorageV1
performs best, followed by
AdPoolAlignOnlyV1
and AllocPool2PercentV1
. This is quite logical: simple
segregated storage minimizes all block operations because it does
not deallocate free blocks on the fly. AdPoolAlignOnlyV1
and AllocPool2PercentV1
perform quite similarly.
When comparing V2 allocators (burst-allocation enabled) we see that performance of all pool allocators is very
similar. The reason for this is that the slightly higher costs of adaptive pools are practically minimized when the pool
allocates several nodes in a row: all needed blocks are preallocated in a single call, error handling in loops can be
simplified leading to tighter loops... Curiously, the performance of a burst-enabled DLmalloc
(AllocatorPlusV2
) is on par with pools with burst allocation. This is not a surprise: DLmalloc burst
allocation uses exactly the same mechanism as pools: allocating big block and create nodes from them. The difference, though,
is in the overhead per node.
When analyzing deallocations, results for V1 allocators are pretty similar, with SimpleSegregatedStorageV1
leading the test. We must remember that SimpleSegregatedStorageV1
does not perform any block managing
and deallocation, so this is the expected behavior. Adaptive pool deallocation times are exactly between DLmalloc
(AllocatorPlusV1
) and segregated storage times. Adaptive pools perform a quite complicated block management
ordering free blocks by free node count and deallocating completely free blocks if the number of them is superior to
a configure value (2 blocks in this test). As expected AdPoolAlignOnlyV2
performs marginally better than
AllocPool2PercentV2
because deallocating a node allocated with AllocPool2PercentV2
(adaptive
pool with sub-blocks) needs an additional indirection to obtain the block header from the node (first we reach the
header of the sub-block and this header stores the address of the block header).
When analyzing burst-enabled allocators, however, the picture changes so that adaptive pools perform similarly to
than SimpleSegregatedStorageV2
. Again, burst-allocation allows the elimination of some redundant checks
and management operations that yield to better performance and amortization of block managing costs.

Now let's see the amount of memory allocated from the operating system by DLmalloc with each allocator
(V1 and V2 practically allocate the same amount of memory so we only represent V2 allocators). DLmalloc
wrapper (AllocatorPlusV2
) allocates more memory than the rest of allocators. Allocated nodes are
12 byte in 32 bit systems so DLmalloc needs 12 byte + overhead (4 bytes) = 16 bytes per node. With 2000000
nodes this yields to aproximately 32 MB. For pools, since overhead is practically inexistent the total memory
is around 24MB (12 bytes per node).
In the previous graph we can see the overhead (in percentage) for each allocator. As expected, DLmalloc
offers a 33% overhead (4 bytes per each 12 byte node) whereas pools offer less than 2% overhead (remember that
we've configured AllocPool2PercentVX
with a maximum of 2 percent overhead). As expected,
SimpleSegregatedStorageVX
offers the minimum overhead but adaptive pools (with their additional
headers for block management) are also very size-efficient.
The previous picture shows how much in-use memory DLmalloc reports after deallocating all the nodes. Note that this does not count the OS memory DLmalloc still caches, but memory that have been allocated through DLmalloc and has not been deallocated yet through DLmalloc. In other words, memory still hold by pools.
As expected DLmalloc wrappers (AllocatorPlusVX
) have deallocated all their memory (no leaks!).
Also, simple segregated storage allocators have not deallocated a single block so they still hold all the memory.
Adaptive pools (AdPoolAlignOnlyVX
and AllocPool2PercentVX
) only hold the number of blocks
we've configured: 2 blocks x 4096 bytes per block = 8192 bytes. So we clearly show that adaptive pools
not only offer a low memory overhead and fast allocation times, but they also return memory to the underlying
memory allocator!
Once allocators return memory to DLmalloc, DLmalloc can trim its cached OS memory and return that memory to the OS. The following graph shows the amount of memory DLmalloc caches after all nodes have been deallocated:
Cached memory usually depends on the number of contiguous free pages that DLmalloc holds internally so numbers are not important. The only thing that this graph shows is that adaptive pools, after returning memory to DLmalloc, encourage also memory trimming so that DLmalloc can return memory to the operating system.
Now we'll execute the same test in a Linux (Suse 10.1) virtual machine (VMWare 6) using gcc-4.1:
Insertion speeds for V1 allocators are more or less the expected with segregated storage leading the group and non-pool DLmalloc wrapper being the slowest one. V2 (burst) allocators are faster with similar performance between adaptive pools and simple segregated storage as the number of the insertion range grows.
Erasure speeds are similar to Windows, with SimpleSegregatedStorageVX
leading the test,
and adaptive pools come next.


Master Terry:
A wise person knows how to be generous to others. Let me share this thought with you: true power can be realized only through true self-discipline.
Learn skills.
Ask about Skill Enchanting.
Quest


WITNESS LIST State Recreational Resources Committee March 10, 1999-8:00A HB 687 For: Kizziar, Geo. H. (Self and Capitol Rod & Gun Club) On: Baker, Bill (Texas Parks and Wildlife Department) Johnston, Dennis (Texas Parks and Wildife Department) Registering, but not testifying: For: Chapman, Dick (Capitol Rod & Gun Club) Cummings, Bill (Texas Silver Haired Legislature) Holtermann, John (Texas Silver Haired Legislature) HCR 23 For: Lusk, Bob (Self)


Talk.
Self-link. For Testing Opera unload, or testing Chrome's "site" grouping.
Start eating CPU (helps determine which process this tab is in)
Stop eating CPU
Start recursive cross-process calling (click this in a non-master tab)


Linear trends and anomalies from annual means of S T max , S T min , and SDTR in China during 1962–2011. Dashed lines are trend lines. K represents the slope (i.e., rate of change (°C/year)); all the slopes of trends were significant ( p < 0.05). Anomaly is the difference between the temperature of one year (corresponding to the X-axis) and the average temperature of 50 years.