Efficient string formatting

Patent metadata

Field	Value
Publication number	US-9639460-B1
Application number	US-201414575779-A
Country	US
Kind code	B1
Filing date	Dec 18, 2014
Priority date	Dec 18, 2014
Publication date	May 2, 2017
Grant date	May 2, 2017

Abstract

A system and method for providing a print formatted string wherein a format object is created for a format string a format string having a set of format specifiers, an amount of memory to allocate to a string buffer for the format object is determined, and the determined amount of memory is allocated to the string buffer. For each set of parameter values received with the format object, where each parameter value corresponds to a format specifier in the format string, a determination is made whether the determined amount of memory for the string buffer is sufficient to hold the set of input parameter values in accordance with the format string. If the determined amount of memory is insufficient, an amount of memory sufficient for the set of input parameter values in accordance with the format string is re-determined, and the string buffer is reallocated to the re-determined amount of memory.

First claim

What is claimed is:

1. A computer-implemented method, comprising:
under the control of one or more computer systems that execute instructions,
in a first phase:
obtaining a format string written in a template language;
identifying:
a first format specifier from the format string, the first format specifier corresponding to a non-dynamic maximum length data type;
a second format specifier from the format string, the second format specifier corresponding to a dynamic maximum length data type; and
string literals from the format string;

computing:
a first memory amount for the first format specifier; and
a second memory amount corresponding to the string literal; and

providing a format object, the format object being a data object configured to:
hold a pointer to a string buffer; and
receive a set of input parameters;

in a second phase:
identifying, by traversing the set of input parameters received by the format object, an input parameter corresponding to the second format specifier;
computing, based at least in part on a value of the input parameter, a third memory amount;
based at least in part on the first memory amount, the second memory amount, and the third memory amount:
determining a total amount of memory to allocate to the string buffer; and
computing corresponding offsets for the string literal, the first format specifier, and the second format specifier; and

allocating the total amount of memory to the string buffer; and

in a third phase, for a plurality of first and second string-formatted values:
inserting into the string buffer corresponding to the pointer of the format object at the corresponding offsets:
a string literal value corresponding to the string literal;
a first string-formatted value corresponding to the first format specifier; and
a second string-formatted value corresponding to the second format specifier; and

performing an operation based at least in part on contents of the string buffer.

2. The computer-implemented method of claim 1 , wherein:
the identifying is performed in a first direction;
the inserting is performed in the first direction; and
the traversing is performed in a second direction different from the first direction.

3. The computer-implemented method of claim 1 , wherein the dynamic maximum length data types are one or more of strings, floating point numbers, and data objects requiring further conversion before display.

4. The computer-implemented method of claim 1 , wherein the format string contains one or more format specifiers indicating how values of the input parameters should be rendered in the string buffer.

5. The computer-implemented method of claim 1 , wherein computing the third memory amount includes:
computing a first required length of a first input parameter of the set of input parameters;
computing, in parallel with computing the first required length, a second required length of a second input parameter of the set of input parameters; and
computing the third memory amount based at least in part on the first required length and the second required length.

6. A system, comprising:
one or more processors; and
memory including instructions that, as a result of execution by the one or more processors, cause the system to:
obtain, a set of format directives with a set of format specifiers;
in a separate thread for each set of input parameter values of a first set of input parameter values, where individual parameter values of the first set of input parameter values correspond to specifiers in the set of format specifiers:
determine a first amount of memory to allocate to a string buffer for the set of format directives; and
allocate the first amount of memory to the string buffer; and

in a separate thread for each set of input parameter values of a second set of input parameter values; where individual parameter values of the second set of input parameter values correspond to the specifiers in the set of format specifiers:
determine whether the first amount of memory allocated to the string buffer is sufficient for the second set of input parameter values; and
on a condition that the first amount of memory is insufficient:
determine a second amount of memory sufficient for the second set of input parameter values; and
allocate the second amount of memory to the string buffer.

7. The system of claim 6 , wherein instructions that cause the system to determine an amount of memory to allocate, further includes instructions that, when executed by the one or more processors, cause the system to determine an amount of memory to allocate to non-dynamic maximum length data types and string literals and determine an amount of memory to allocate to input parameters corresponding to dynamic maximum length data types.

8. The system of claim 6 , wherein the instructions further include instructions that cause the system to:
determine a predetermined amount of memory to pre-allocate to the string buffer based at least in part on required lengths for format placeholders corresponding to non-dynamic maximum length data types, required lengths for string literals, and default lengths for dynamic maximum length data types specified in the set of format directives;
allocate the predetermined amount of memory to the string buffer; and
the instructions that cause the system to determine the first amount of memory further include instructions that determine a first amount of memory based at least in part on whether the predetermined amount of memory is insufficient for the first set of input parameter values.

9. The system of claim 6 , wherein an unused portion of memory allocated to the string buffer is usable as temporary scratch space.

10. The system of claim 6 , wherein:
the instructions further include instructions that cause the system to cause the system to track a weighted average of memory sufficient for the set of input parameters; and
the instructions that cause the system to reallocate the string buffer, include instructions that, when executed by the one or more processors, cause the system to allocate the second amount of memory to a temporary string buffer for the set of format directives and the set of input parameter values if the second amount of memory exceeds a threshold amount above the weighted average.

11. The system of claim 6 , wherein instructions that cause the system to determine whether the first amount of memory is sufficient, further includes instructions that cause the system to determine, based at least in part on whether required lengths for placeholders corresponding to non-dynamic maximum length data types and string literals and required lengths for the set of input parameter values would exceed the first amount of memory.

12. The system of claim 6 , wherein the instructions further include instructions that cause the system to create a format object for the set of format directives, wherein the format object receives a pointer to the string buffer.

13. The system of claim 6 , wherein the instructions further include instructions that cause the system to:
convert the first set of input parameter values into a first set of strings;
write the first set of strings into the string buffer in accordance with the set of format directives;
convert the second set of input parameter values into a second set of strings;
write the second set of strings into the string buffer in accordance with the set of format directives; and
output the string buffer.

14. A non-transitory computer-readable storage medium having stored thereon executable instructions that, as a result of execution by one

Assignees

• Amazon Tech Inc

Inventors

• Karppanen Jari Juhani

Classifications

• G06F2212/1016

  Performance improvement · CPC title

• G06F2212/1044

  Space efficiency improvement · CPC title

• G06F12/023 Primary

  Free address space management · CPC title