REAL-TIME REDUCTION OF CPU OVERHEAD FOR DATA COMPRESSION

• US 20140195498A1
• Filed: 01/10/2013
• Published: 07/10/2014
• Est. Priority Date: 01/10/2013
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: ASHER, Ron, HARNIK, Danny, MARGALIT, Oded, RONEN, Kat I., SOTNIKOV, Dmitry
• Granted Patent: US 9,564,918 B2
• Time in Patent Office: Days
• US Class Current: 707/693
• CPC Class Codes: H03M 7/4037 Prefix coding
• CPC Class Codes: H03M 7/607 Selection between different types of compressors
• CPC Class Codes: H03M 7/6088 according to the data type

Abstract

Real-time reduction of CPU overhead for data compression is performed by a processor device in a computing environment. Non-compressing heuristics are applied on a randomly selected data sample from data sequences for determining whether to compress the data sequences. A compression potential is calculated based on the non-compressing heuristics. The compression potential is compared to a threshold value. The data sequences are either compressed if the compress threshold is matched, compressed using Huffman coding if Huffman coding threshold is matched, or stored without compression.

Claims

1. A method for real-time reduction of CPU overhead for data compression by a processor device in a computing environment, the method comprising:

applying non-compressing heuristics on a randomly selected data sample from data sequences for determining whether to compress the data sequences by calculating a compression potential based on the non-compressing heuristics, wherein the compression potential is compared to a threshold value; and

performing one of;

compressing the data sequences if the compress threshold is matched,

compressing the data sequences using Huffman coding if Huffman coding threshold is matched, and

storing the data sequences without compression.

2. The method of claim 1, further including:

using at least one of the non-compressing heuristics,

selecting a randomly selected data sample, and

computing core characters that compose a predefined percentage of bytes in the randomly selected data sample, an entropy of the data, a relation between appearances of character pairs and a random distribution of the character pairs, and the entropy of the character pairs for determining whether to compress the data sequences.

3. The method of claim 1, further including calculating the non-compressing heuristics one after another for developing a heuristic score for making a decision for determining whether to compress the data sequences, wherein the CPU speed is optimized.

4. The method of claim 3, further including calculating the compression potential based on the heuristic score of the non-compressing heuristics.

5. The method of claim 1, further including:

estimating a relation between appearances of character pairs and a random distribution of the character pairs by;

comparing a number of pairs from core characters in the randomly selected data sample against the number of pairs from the core characters expected to appear in a random distribution in the randomly selected data sample, and

calculating a L² norm distance between a first vector of distributions representing an observed distribution of the number of pairs from the core characters in the randomly selected data sample and a second vector of distributions representing an expected distribution of single values assuming there is no correlation between subsequent pairs from the core characters.

6. The method of claim 1, further including performing one of turning off and turning on the calculating the compression potential, and determining whether to compress the data sequences according to a predefined setting.

7. The method of claim 1, wherein the predefined setting, further includes at least one of:

continuously applying the non-compressing heuristics and providing an indication as to whether to compress the data sequences,

applying the non-compressing heuristics on demand when a compression ratio is above the predetermined threshold for a predefined number of the data sequences,

applying the non-compressing heuristics according to a size of the buffer, and

applying a prefix compression estimation and deciding whether to compress the data sequences based on a prefix compression ratio when the prefix compression ratio of the data sequences is below a threshold.

8. The method of claim 1, further including applying the non-compressing heuristics to a relation between character pairs of core characters and random distributions of the character pairs of the core characters from the randomly selected data sample from data sequences for determining whether to compress the data sequences by calculating the compression potential based on the non-compressing heuristics.

9. A system for real-time reduction of CPU overhead for data compression in a computing environment, the system comprising:

a processor device operable in the computing storage environment, wherein the processor device;

applies non-compressing heuristics on a randomly selected data sample from data sequences for determining whether to compress the data sequences by calculating a compression potential based on the non-compressing heuristics, wherein the compression potential is compared to a threshold value, and

performs one of;

compressing the data sequences if the compress threshold is matched,

compressing the data sequences using Huffman coding if Huffman coding threshold is matched, and

storing the data sequences without compression.

10. The system of claim 9, wherein the processor device:

uses at least one of the non-compressing heuristics,

selects a randomly selected data sample, and

computes core characters that compose a predefined percentage of bytes in the randomly selected data sample, an entropy of the data, a relation between appearances of character pairs and a random distribution of the character pairs, and the entropy of the character pairs for determining whether to compress the data sequences.

11. The system of claim 10, wherein the processor device calculates the non-compressing heuristics one after another for developing a heuristic score for making a decision for determining whether to compress the data sequences, wherein the CPU speed is optimized.

12. The system of claim 11, wherein the processor device calculates the compression potential based on the heuristic score of the non-compressing heuristics.

13. The system of claim 10, wherein the processor device:

estimates a relation between appearances of character pairs and a random distribution of the character pairs by;

comparing a number of pairs from core characters in the randomly selected data sample against the number of pairs from the core characters expected to appear in a random distribution in the randomly selected data sample, and

calculating a L² norm distance between a first vector of distributions representing an observed distribution of the number of pairs from the core characters in the randomly selected data sample and a second vector of distributions representing an expected distribution of single values assuming there is no correlation between subsequent pairs from the core characters.

14. The system of claim 10, wherein the processor device performs one of turning off and turning on the calculating the compression potential, and determining whether to compress the data sequences according to a predefined setting.

15. The system of claim 10, wherein the processor device performs at least one of:

continuously applying the non-compressing heuristics and providing an indication as to whether to compress the data sequences,

applying the non-compressing heuristics on demand when a compression ratio is above the predetermined threshold for a predefined number of the data sequences,

applying the non-compressing heuristics according to a size of the buffer, and

applying a prefix compression estimation and deciding whether to compress the data sequences based on a prefix compression ratio when the prefix compression ratio of the data sequences is below a threshold.

16. The system of claim 10, wherein the processor device applies the non-compressing heuristics to a relation between character pairs of core characters and random distributions of the character pairs of the core characters from the randomly selected data sample from data sequences for determining whether to compress the data sequences by calculating the compression potential based on the non-compressing heuristics.

17. A computer program product for real-time reduction of CPU overhead for data compression by a processor device by a processor device, the computer program product comprising a computer-readable storage medium having computer-readable program code portions stored therein, the computer-readable program code portions comprising:

a first executable portion that applies non-compressing heuristics on a randomly selected data sample from data sequences for determining whether to compress the data sequences by calculating a compression potential based on the non-compressing heuristics, wherein the compression potential is compared to a threshold value, and

a second executable portion that performs one of;

compressing the data sequences if the compress threshold is matched,

compressing the data sequences using Huffman coding if Huffman coding threshold is matched, and

storing the data sequences without compression.

18. The computer program product of claim 17, further including a third executable portion that:

uses at least one of the non-compressing heuristics,

selects a randomly selected data sample, and

computes core characters that compose a predefined percentage of bytes in the randomly selected data sample, an entropy of the data, a relation between appearances of character pairs and a random distribution of the character pairs, and the entropy of the character pairs for determining whether to compress the data sequences.

19. The computer program product of claim 17, further including a third executable portion that calculates the non-compressing heuristics one after another for developing a heuristic score for making a decision for determining whether to compress the data sequences, wherein the CPU speed is optimized.

20. The computer program product of claim 19, further including a fourth executable portion that calculates the compression potential based on the heuristic score of the non-compressing heuristics.

21. The computer program product of claim 17, further including a third executable portion that:

estimates a relation between appearances of character pairs and a random distribution of the character pairs by;

comparing a number of pairs from core characters in the randomly selected data sample against the number of pairs from the core characters expected to appear in a random distribution in the randomly selected data sample, and

calculating a L² norm distance between a first vector of distributions representing an observed distribution of the number of pairs from the core characters in the randomly selected data sample and a second vector of distributions representing an expected distribution of single values assuming there is no correlation between subsequent pairs from the core characters.

22. The computer program product of claim 17, further including a third executable portion that performs one of turning off and turning on the calculating the compression potential, and determining whether to compress the data sequences according to a predefined setting.

23. The computer program product of claim 17, further including a third executable portion that performs at least one of:

continuously applying the non-compressing heuristics and providing an indication as to whether to compress the data sequences,

applying the non-compressing heuristics on demand when a compression ratio is above the predetermined threshold for a predefined number of the data sequences,

applying the non-compressing heuristics according to a size of the buffer, and

applying a prefix compression estimation and deciding whether to compress the data sequences based on a prefix compression ratio when the prefix compression ratio of the data sequences is below a threshold.

24. The computer program product of claim 17, further including a third executable portion that applies the non-compressing heuristics to a relation between character pairs of core characters and random distributions of the character pairs of the core characters from the randomly selected data sample from data sequences for determining whether to compress the data sequences by calculating the compression potential based on the non-compressing heuristics.