System and Method for Implementing Shared Probabilistic Counters Storing Update Probability Values

A system comprising:

• one or more processors that support multithreading;
• a memory storing program instructions that when executed on the one or more processors cause the one or more processors to perform:
• beginning execution of a multithreaded application that comprises one or more operations to increment a shared counter, wherein the shared counter is implemented as a data structure that is accessible by a plurality of threads of the multithreaded application, wherein the data structure stores a representation of an update probability value, wherein the update probability value indicates a probability that the representation of the update probability value will be updated in response to initiation of an increment operation targeting the shared counter, and wherein a projected value of the shared counter is computable based at least in part on the representation of the update probability value;
• initiating, by a given thread of the application, an increment operation targeting the shared counter;
• in response to said initiating, determining whether to perform the increment operation, wherein said determining is dependent, at least in part, on the representation of the update probability stored in the data structure;
• and
• in response to determining that the increment operation is to be performed, updating the representation of the update probability value stored in the data structure, wherein the updated representation represents a probability that the updated representation of the update probability value stored in the data structure will be further updated in response to initiation of a subsequent increment operation;
• wherein one or more of said determining whether to perform the increment operation or said updating the representation of the update probability value are dependent on a pre-determined value of a configurable accuracy parameter.

A non-transitory, computer readable storage medium storing program instructions that when executed on one or more computers cause the one or more computers to perform:

• beginning execution of a multithreaded application that comprises one or more operations to increment a shared counter, wherein the shared counter is implemented as a data structure that is accessible by a plurality of threads of the multithreaded application, wherein the data structure stores a representation of an update probability value, wherein the update probability value indicates a probability that the representation of the update probability value will be updated in response to initiation of an increment operation targeting the shared counter, and wherein a projected value of the shared counter is computable based at least in part on the representation of the update probability value;
• initiating, by a given thread of the application, an increment operation targeting the shared counter;
• in response to said initiating, determining whether to perform the increment operation, wherein said determining is dependent, at least in part, on the representation of the update probability stored in the data structure;
• and
• in response to determining that the increment operation is to be performed, updating the representation of the update probability value stored in the data structure, wherein the updated representation represents a probability that the updated representation of the update probability value stored in the data structure will be further updated in response to initiation of a subsequent increment operation;
• wherein one or more of said determining whether to perform the increment operation or said updating the representation of the update probability value are dependent on a pre-determined value of a configurable accuracy parameter.