Multi-threaded sort of data items in spreadsheet tables

• US 8,527,866 B2
• Filed: 04/30/2010
• Issued: 09/03/2013
• Est. Priority Date: 04/30/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Sutter, Carl B. IV, Grabar, Anatoly V., Rothschiller, Chad B.
• Primary Examiner(s): Mills, Frank D
• Application Number:
  US12/771,164
• Publication Number:
  US 20110271282A1
• Time in Patent Office: 1,222 Days
• Field of Search: 715/212
• US Class Current: 715/212
• CPC Class Codes: G06F 2209/5017 Task decomposition
• CPC Class Codes: G06F 2209/5018 Thread allocation
• CPC Class Codes: G06F 40/18 of spreadsheets form-filling G06F40/174
• CPC Class Codes: G06F 9/5027 the resource being a machine, e.g. CPUs, Servers, Terminals

Abstract

To sort data items in a spreadsheet table, data items in the spreadsheet table are divided into a plurality of blocks. Multiple threads are used to sort the data items in the blocks. After the data items in the blocks are sorted, multiple merge threads are used to generate a final result block. The final result block contains each of the data items in the spreadsheet table. Each of the merge threads is a thread that merges two source blocks to generate a result block. Each of the source blocks is either one of the sorted blocks or one of the result blocks generated by another one of the merge threads. A sorted version of the spreadsheet table is then displayed. The data items in the sorted version of the spreadsheet table are ordered according to an order of the data items in the final result block.

Claims

1. A method comprising:

dividing data items in a spreadsheet table into a plurality of blocks;

using multiple threads to sort the data items in the blocks;

after the data items in the blocks are sorted, using, by a computing system, multiple merge threads to generate a final result block, the final result block containing each of the data items in the spreadsheet table, each of the merge threads being a thread that merges two source blocks to generate a result block, each of the source blocks being either one of the sorted blocks or one of the result blocks generated by another one of the merge threads;

displaying a sorted version of the spreadsheet table, data items in the sorted version of the spreadsheet table being ordered according to an order of the data items in the final result block; and

determining an appropriate number of blocks based on a minimum job size and the number of processing units in a processing system, the appropriate number of blocks being equal to a number of rows in the spreadsheet table divided by the minimum job size rounded down when the number of rows divided by the minimum job size is less than or equal to a number of processing units in the computing system.

2. The method of claim 1, further comprising:

presenting a user interface that allows an administrative user to set the minimum job size.

3. The method of claim 1, further comprising:

determining, by the computing system, whether the number of data items in the spreadsheet table exceeds a lower limit; and

using a single thread to generate the final result block when the number of data items in the spreadsheet table does not exceed the lower limit.

4. The method of claim 1,

wherein one of the merge threads is an incomplete interior thread when the number of blocks in the plurality of blocks is odd;

wherein the method further comprises;

assigning one of the blocks to the incomplete interior thread;

wherein the result block generated by the incomplete interior thread contains each of the data items in a result block generated by a child thread of the incomplete interior thread and the block assigned to the incomplete interior thread, the data items in the result block generated by the incomplete interior thread being properly ordered.

5. The method of claim 4, wherein the incomplete interior thread performs at least the following actions:

determining whether there are any remaining data items in a first block, the first block being the result block generated by the child thread of the incomplete interior thread;

performing the following actions when there are one or more remaining data items in the first block;

determining whether there are any remaining data items in a second block, the second block being assigned to the incomplete interior thread;

performing the following actions when there are one or more remaining data items in the second block;

identifying a minimum data item, the minimum data item being the smallest of the remaining data items in the first block and the second block;

inserting the minimum data item into the result block following the largest data item in the result block generated by the incomplete interior thread;

inserting, when there are no remaining data items in the second block, any remaining data items in the first block into the result block generated by the incomplete interior thread following the largest data item in the result block generated by the incomplete interior thread;

determining, when there are no remaining data items in the second block, whether the child thread is done;

waiting, when the child thread is not done, until the child thread adds another data item to the second block;

inserting, when the child thread is done, any remaining data items in the second block into the result block generated by the incomplete interior thread following the largest data item in the result block generated by the incomplete interior thread.

6. The method of claim 1, wherein the merge thread include a parent thread that starts generating a result block before child threads of the parent thread are finished generating their result blocks, the child threads of the parent thread being other ones of the merge threads.

7. The method of claim 1, wherein the merge threads include a leaf thread that performs the following actions:

determining whether there are any remaining data items in a first block assigned to the leaf thread, the first block being one of the sorted blocks;

performing the following actions while there are one or more data items in the first block;

determining whether there are any remaining data items in a second block assigned to the leaf thread, the second block being another one of the sorted blocks;

performing the following actions when there are one or more data items in the second block;

identifying a minimum data item, the minimum data item being a smallest of the remaining data item in the first block and the second block;

inserting the minimum data item into a result block generated by the leaf thread after a largest data item in the result block;

inserting, when there are no remaining data items in the second block, any remaining data items in the first block into the result block generated by the leaf thread after the largest data item in the result block generated by the leaf thread;

inserting, when there are no remaining data items in the first block, any remaining data items in the second block into the result block after the largest data item in the result block generated by the leaf thread.

8. The method of claim 7, wherein the leaf thread performs the following actions in response to being woken:

determining whether a largest data item in the first block is smaller than a smallest data item in the second block;

performing, when the largest data item in the first block is smaller than the smallest data item in the second block, at least the following actions without comparing additional data items in the first block and the second block;

inserting the data items in the first block into the result block generated by the leaf thread; and

inserting the data items in the second block into the result block after a largest data item in the result block generated by the leaf thread;

determining whether a largest data item in the second block is smaller than a smallest data item in the first block;

performing, when the largest data item in the second block is smaller than the smallest data item in the first block, at least the following actions without comparing additional data items in the first block and the second block;

inserting the data items in the second block into the result block generated by the leaf thread; and

inserting the data items in the first block into the result block after a largest data item in the result block generated by the leaf thread.

9. The method of claim 1, wherein displaying the sorted version of the spreadsheet table comprises sending result data to a client device via a communications network, the client device configured to process the result data to display the sorted version of the spreadsheet table to a user.

10. The method of claim 1, wherein the spreadsheet table is a pivot table.

11. The method of claim 1, wherein the result data is a version of the spreadsheet table in which the data items in the spreadsheet table are properly ordered.

12. A computing system comprising:

a processing system comprising a plurality of processing units; and

a data storage system comprising computer-readable instructions that, when executed by one or more of the processing units, cause the computing system to;

divide data items in a spreadsheet table into a plurality of blocks;

use multiple block sorting threads to sort the data items in the blocks, wherein the number of the block sorting threads is equal to the number of the blocks;

after the data items in the blocks are sorted, use multiple merge threads to generate a final result block, the final result block containing each of the data items in the spreadsheet table, each of the merge threads being a thread that merges two source blocks to generate a result block, each of the source blocks being either one of the sorted blocks or one of the result blocks generated by another one of the merge threads; and

display a sorted version of the spreadsheet table, data items in the sorted version of the spreadsheet table being ordered according to an order of the data items in the final result block, wherein the merge threads include an incomplete interior thread when the number of blocks in the plurality of blocks is odd, wherein the computer-readable instructions, when executed by one or more of the processing units, further cause the computing system to assign one of the blocks to the incomplete interior thread, wherein the incomplete interior thread generates a result block that contains each of the data items in a result block generated by a child thread of the incomplete interior thread and the block assigned to the incomplete interior thread, the data items in the result block generated by the incomplete interior thread being properly ordered, the child thread being another one of the merge threads.

13. The computing system of claim 12, wherein the computer-readable instructions, when executed by one or more of the processing units, cause the computing system to determine an appropriate number of blocks based on a minimum job size and the number of processing units in the processing system, the appropriate number of blocks being equal to a number of the plurality of processing units in the computing system when a number of rows in the spreadsheet table divided by the minimum job size is greater than or equal to the number of the plurality of processing units in the processing system.

14. The computing system of claim 12, wherein the computer-readable instructions, when executed by one or more of the processing units, cause the computing system to:

determine whether the number of data items in the spreadsheet table exceeds a lower limit; and

use a single thread to generate the final result block when the number of data items in the spreadsheet table does not exceed the lower limit.

15. The computing system of claim 12, wherein the computer-readable instructions represent a spreadsheet application.

16. The computing system of claim 12, wherein the merge threads further include a parent thread that starts generating a result block before child threads of the parent thread are finished generating their result blocks, the child threads of the parent thread being other ones of the merge threads.

17. The computing system of claim 12, wherein the spreadsheet table is a pivot table.

18. A method comprising:

dividing data items in a spreadsheet table into a plurality of blocks;

using multiple threads to sort the data items in the blocks;

after the data items in the blocks are sorted, using, by a computing system, multiple merge threads to generate a final result block, the final result block containing each of the data items in the spreadsheet table, each of the merge threads being a thread that merges two source blocks to generate a result block, each of the source blocks being either one of the sorted blocks or one of the result blocks generated by another one of the merge threads, the merge threads including a leaf thread that performs the following actions;

determining whether there are any remaining data items in a first block assigned to the leaf thread, the first block being one of the sorted blocks;

performing the following actions while there are one or more data items in the first block;

determining whether there are any remaining data items in a second block assigned to the leaf thread, the second block being another one of the sorted blocks;

performing the following actions when there are one or more data items in the second block;

identifying a minimum data item, the minimum data item being a smallest of the remaining data item in the first block and the second block;

inserting the minimum data item into a result block generated by the leaf thread after a largest data item in the result block;

inserting, when there are no remaining data items in the second block, any remaining data items in the first block into the result block generated by the leaf thread after the largest data item in the result block generated by the leaf thread; and

inserting, when there are no remaining data items in the first block, any remaining data items in the second block into the result block after the largest data item in the result block generated by the leaf thread; and

displaying a sorted version of the spreadsheet table, data items in the sorted version of the spreadsheet table being ordered according to an order of the data items in the final result block.