Allow developer to resize the dictionary ?

[penguin-wwy]

In many scenarios, a dictionary is used to cache something. For example, pyspark access spark object by py4j, in python code, every JavaObject need to cache JavaMember which can be accessed.

class JavaObject(object):
    def __init__(self, target_id, gateway_client):
        ...
        self._methods = {}
        ...

    def __getattr__(self, name):
        if is_magic_member(name):
            # don't propagate any magic methods to Java
            raise AttributeError

        if name not in self._methods:
            if (self._auto_field):
                (is_field, return_value) = self._get_field(name)
                if (is_field):
                    self._field_names.add(name)
                    return return_value
            # Theoretically, not thread safe, but the worst case scenario is
            # cache miss or double overwrite of the same method...
            self._methods[name] = JavaMember(
                name, self, self._target_id, self._gateway_client)

        # The name is a method
        return self._methods[name]

The number of objects that need to be cached can be expected in this situation. So, if the developer case resize the cache dictionary, the dictresize during insertdict can be reduced.

I test micro-benchmark for insert operations between resized-new dict and common-new dict

import cProfile


def only_test_insert(cases, dict_list):
    for d in dict_list:
        for i in cases:
            d[i] = i


if __name__ == "__main__":
    loop = 100000

    # TEST INSERT 120 TIMES
    cases = [i for i in range(120)]
    d1 = [ {} for _ in range(0, 100000)]
    d2 = [ {}.resize(len(cases)) for _ in range(0, 100000)]
    cProfile.run("only_test_insert(cases, d1)")
    cProfile.run("only_test_insert(cases, d2)")

    # TEST INSERT 1000 TIMES
    cases = [i for i in range(1000)]
    d1 = [{} for _ in range(0, 100000)]
    d2 = [{}.resize(len(cases)) for _ in range(0, 100000)]
    cProfile.run("only_test_insert(cases, d1)")
    cProfile.run("only_test_insert(cases, d2)")

TEST INSERT 120 TIMES

         4 function calls in 0.078 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.078    0.078 <string>:1(<module>)
        1    0.078    0.078    0.078    0.078 resize_dict.py:4(only_test_insert)
        1    0.000    0.000    0.078    0.078 {built-in method builtins.exec}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}


         4 function calls in 0.067 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.067    0.067 <string>:1(<module>)
        1    0.067    0.067    0.067    0.067 resize_dict.py:4(only_test_insert)
        1    0.000    0.000    0.067    0.067 {built-in method builtins.exec}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}

TEST INSERT 1000 TIMES

         4 function calls in 0.613 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.613    0.613 <string>:1(<module>)
        1    0.613    0.613    0.613    0.613 resize_dict.py:4(only_test_insert)
        1    0.000    0.000    0.613    0.613 {built-in method builtins.exec}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}


         4 function calls in 0.559 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.559    0.559 <string>:1(<module>)
        1    0.559    0.559    0.559    0.559 resize_dict.py:4(only_test_insert)
        1    0.000    0.000    0.559    0.559 {built-in method builtins.exec}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}

Speed up ~10%

---

Edit 1:

def test_create_and_insert1(cases):
    for _ in range(10000):
        d = {}
        for i in cases:
            d[i] = i


def test_create_and_insert2(cases):
    for _ in range(10000):
        d = {}.resize(1000)
        for i in cases:
            d[i] = i

if __name__ == "__main__":
    cases = [i for i in range(1000)]
    cProfile.run("test_create_and_insert1(cases)")
    cProfile.run("test_create_and_insert2(cases)")

TEST CREATE DICT AND INSERT 1000 TIMES

         4 function calls in 0.573 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.573    0.573 <string>:1(<module>)
        1    0.573    0.573    0.573    0.573 resize_dict.py:10(test_create_and_insert1)
        1    0.000    0.000    0.573    0.573 {built-in method builtins.exec}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}


         10004 function calls in 0.543 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.543    0.543 <string>:1(<module>)
        1    0.539    0.539    0.543    0.543 resize_dict.py:17(test_create_and_insert2)
        1    0.000    0.000    0.543    0.543 {built-in method builtins.exec}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
    10000    0.004    0.000    0.004    0.000 {method 'resize' of 'dict' objects}

Speed up 4~5%

[methane]

~10% speedup on microbench is not so nice.

JavaMember(name, self, self._target_id, self._gateway_client) will be much much more slower than dictresize.

[penguin-wwy]

py4j access jvm by socket, for the whole program the bottleneck is not dict. However, allow resize maybe help improve performance in other scenarios and is not costly :)

[methane]

I don't think so.

Your benchmark is not good because you exclude cost of {} and .resize(len(cases)).

And even your extreme microbenchmark shows only 10% difference.
I expect no significant improvement in real scenario. (Or it is slower because of .resize(len(x)))

[penguin-wwy]

You are right. I append test create_and_insert.

Assume that for 120 insertions, the insert operation brings in at least 4 resize op (8 -> 16 -> 32 -> 64 -> 128).

For the case of more insert operations, the cost of the insertion itself may lead to a relative reduction in the benefit of the reduced resize operation.

So I approve that no significant improvement in real scenario, but on the other hand it at least provides an alternative operation that is not worse.

Thanks again for your review ：）