From 9de215db31bc6e8f4becf7058d33fe1d82b0ac9f Mon Sep 17 00:00:00 2001 From: Taras Tsugrii Date: Tue, 17 Jul 2018 08:56:13 -0700 Subject: [Skylark] Make range function lazy. range used to use MutableList which would eagerly allocate an array list with all range elements, which is not efficient for very large ranges or when only a small number of its elements are used. This implementation uses a constant amount of RAM and computes a value for each requested index. For the following Skylark snippet: ``` def check_content(t): if t == []: return t return False def modulo(n): return n % 797 N = 10000000 [check_content(i) for i in range(N)] [check_content(i) for i in range(N)] [modulo(i) for i in range(N)] [modulo(i) for i in range(N)] ``` the total runtime goes from ``` $ time bazel-bin/src/main/java/com/google/devtools/skylark/Skylark test.bzl bazel-bin/src/main/java/com/google/devtools/skylark/Skylark test.bzl 93.09s user 1.67s system 316% cpu 29.930 total ``` to ``` $ time bazel-bin/src/main/java/com/google/devtools/skylark/Skylark test.bzl bazel-bin/src/main/java/com/google/devtools/skylark/Skylark test.bzl 31.45s user 0.86s system 179% cpu 17.974 total ``` which reflects the reduced system time (fewer allocations) and performance. Closes #5240. PiperOrigin-RevId: 204918577 --- .../packages/SkylarkSemanticsConsistencyTest.java | 2 + .../build/lib/syntax/MethodLibraryTest.java | 53 ++++++++++++++++++++++ 2 files changed, 55 insertions(+) (limited to 'src/test/java/com/google/devtools/build') diff --git a/src/test/java/com/google/devtools/build/lib/packages/SkylarkSemanticsConsistencyTest.java b/src/test/java/com/google/devtools/build/lib/packages/SkylarkSemanticsConsistencyTest.java index a96d928283..893d5d44a5 100644 --- a/src/test/java/com/google/devtools/build/lib/packages/SkylarkSemanticsConsistencyTest.java +++ b/src/test/java/com/google/devtools/build/lib/packages/SkylarkSemanticsConsistencyTest.java @@ -135,6 +135,7 @@ public class SkylarkSemanticsConsistencyTest { "--incompatible_new_actions_api=" + rand.nextBoolean(), "--incompatible_no_support_tools_in_action_inputs=" + rand.nextBoolean(), "--incompatible_package_name_is_a_function=" + rand.nextBoolean(), + "--incompatible_range_type=" + rand.nextBoolean(), "--incompatible_remove_native_git_repository=" + rand.nextBoolean(), "--incompatible_remove_native_http_archive=" + rand.nextBoolean(), "--incompatible_string_is_not_iterable=" + rand.nextBoolean(), @@ -164,6 +165,7 @@ public class SkylarkSemanticsConsistencyTest { .incompatibleNewActionsApi(rand.nextBoolean()) .incompatibleNoSupportToolsInActionInputs(rand.nextBoolean()) .incompatiblePackageNameIsAFunction(rand.nextBoolean()) + .incompatibleRangeType(rand.nextBoolean()) .incompatibleRemoveNativeGitRepository(rand.nextBoolean()) .incompatibleRemoveNativeHttpArchive(rand.nextBoolean()) .incompatibleStringIsNotIterable(rand.nextBoolean()) diff --git a/src/test/java/com/google/devtools/build/lib/syntax/MethodLibraryTest.java b/src/test/java/com/google/devtools/build/lib/syntax/MethodLibraryTest.java index 072b9c8e1c..103a35d137 100644 --- a/src/test/java/com/google/devtools/build/lib/syntax/MethodLibraryTest.java +++ b/src/test/java/com/google/devtools/build/lib/syntax/MethodLibraryTest.java @@ -486,6 +486,14 @@ public class MethodLibraryTest extends EvaluationTestCase { .testStatement("str(range(5, 0, -1))", "[5, 4, 3, 2, 1]") .testStatement("str(range(5, 0, -10))", "[5]") .testStatement("str(range(0, -3, -2))", "[0, -2]") + .testStatement("str(range(5)[1:])", "[1, 2, 3, 4]") + .testStatement("len(range(5)[1:])", 4) + .testStatement("str(range(5)[:2])", "[0, 1]") + .testStatement("str(range(10)[1:9:2])", "[1, 3, 5, 7]") + .testStatement("str(range(10)[1:10:2])", "[1, 3, 5, 7, 9]") + .testStatement("str(range(10)[1:11:2])", "[1, 3, 5, 7, 9]") + .testStatement("str(range(0, 10, 2)[::2])", "[0, 4, 8]") + .testStatement("str(range(0, 10, 2)[::-2])", "[8, 4, 0]") .testIfErrorContains("step cannot be 0", "range(2, 3, 0)"); } @@ -499,6 +507,51 @@ public class MethodLibraryTest extends EvaluationTestCase { runRangeIsListAssertions("range(4)[:3]"); } + @Test + public void testRangeType() throws Exception { + new BothModesTest("--incompatible_range_type=true") + .setUp("a = range(3)") + .testStatement("len(a)", 3) + .testStatement("str(a)", "range(0, 3)") + .testStatement("str(range(1,2,3))", "range(1, 2, 3)") + .testStatement("repr(a)", "range(0, 3)") + .testStatement("repr(range(1,2,3))", "range(1, 2, 3)") + .testStatement("type(a)", "range") + .testIfErrorContains("unsupported operand type(s) for +: 'range' and 'range'", "a + a") + .testIfErrorContains("type 'range' has no method append(int)", "a.append(3)") + .testStatement("str(list(range(5)))", "[0, 1, 2, 3, 4]") + .testStatement("str(list(range(0)))", "[]") + .testStatement("str(list(range(1)))", "[0]") + .testStatement("str(list(range(-2)))", "[]") + .testStatement("str(list(range(-3, 2)))", "[-3, -2, -1, 0, 1]") + .testStatement("str(list(range(3, 2)))", "[]") + .testStatement("str(list(range(3, 3)))", "[]") + .testStatement("str(list(range(3, 4)))", "[3]") + .testStatement("str(list(range(3, 5)))", "[3, 4]") + .testStatement("str(list(range(-3, 5, 2)))", "[-3, -1, 1, 3]") + .testStatement("str(list(range(-3, 6, 2)))", "[-3, -1, 1, 3, 5]") + .testStatement("str(list(range(5, 0, -1)))", "[5, 4, 3, 2, 1]") + .testStatement("str(list(range(5, 0, -10)))", "[5]") + .testStatement("str(list(range(0, -3, -2)))", "[0, -2]") + .testStatement("range(3)[-1]", 2) + .testIfErrorContains( + "index out of range (index is 3, but sequence has 3 elements)", "range(3)[3]") + .testStatement("str(range(5)[1:])", "range(1, 5)") + .testStatement("len(range(5)[1:])", 4) + .testStatement("str(range(5)[:2])", "range(0, 2)") + .testStatement("str(range(10)[1:9:2])", "range(1, 9, 2)") + .testStatement("str(list(range(10)[1:9:2]))", "[1, 3, 5, 7]") + .testStatement("str(range(10)[1:10:2])", "range(1, 10, 2)") + .testStatement("str(range(10)[1:11:2])", "range(1, 10, 2)") + .testStatement("str(range(0, 10, 2)[::2])", "range(0, 10, 4)") + .testStatement("str(range(0, 10, 2)[::-2])", "range(8, -2, -4)") + .testStatement("str(range(5)[1::-1])", "range(1, -1, -1)") + .testIfErrorContains("step cannot be 0", "range(2, 3, 0)") + .testIfErrorContains( + "unsupported operand type(s) for *: 'range' and 'int'", "range(3) * 3"); + ; + } + /** * Helper function for testRangeIsList that expects a range or range slice expression producing * the range value containing [0, 1, 2]. -- cgit v1.2.3