Cache constant frozen-sets

[scoder]

Some set constants can be replaced by frozensets, e.g. in cases like x in {1,2,3}. This would allow them to become global constants, created once at module init time. There is already a framework for merging tuple and string constants, see TupleNode. The ConstantFolding transformation could detect these cases and set a flag attribute on the SetNode instances that would trigger constant frozenset behaviour.

Other potential candidates:

>>> frozenset((1,2,3)) | {2,3,4}  # imagine one side being non-constant
frozenset([1, 2, 3, 4])
>>> {3,4,5} | frozenset((1,2,3))
set([1, 2, 3, 4, 5])

[Endle]

Hi scoder. I'm new to cython and I'm interested in this issue
As you mentioned, we're already deduping tuple constants.

For example. in this case

def f():
    a = (1, 2, 3)
    b = (1, 2, 3)

We're referring to the same object

  /* "tuple.pyx":2
 * def f():
 *     a = (1, 2, 3)             # <<<<<<<<<<<<<<
 *     b = (1, 2, 3)
 * 
 */
  __Pyx_INCREF(__pyx_tuple_);
  __pyx_v_a = __pyx_tuple_;

  /* "tuple.pyx":3
 * def f():
 *     a = (1, 2, 3)
 *     b = (1, 2, 3)             # <<<<<<<<<<<<<<
 * 
 * #a = {1, 2, 3}
 */
  __Pyx_INCREF(__pyx_tuple_);
  __pyx_v_b = __pyx_tuple_;

I'm reading the code for TupleNode and I found

        if self.is_literal or self.is_partly_literal:
            # The "mult_factor" is part of the deduplication if it is also constant, i.e. when
            # we deduplicate the multiplied result.  Otherwise, only deduplicate the constant part.
            dedup_key = make_dedup_key(self.type, [self.mult_factor if self.is_literal else None] + self.args)
            tuple_target = code.get_py_const(py_object_type, 'tuple', cleanup_level=2, dedup_key=dedup_key)
            const_code = code.get_cached_constants_writer(tuple_target)
            if const_code is not None:
                # constant is not yet initialised
                const_code.mark_pos(self.pos)
                self.generate_sequence_packing_code(const_code, tuple_target, plain=not self.is_literal)
                const_code.put_giveref(tuple_target, py_object_type)

Is here the place for deduping tuple. and I should go deeper for code at here?

Thank you!

[da-woods]

@Endle That definitely looks right to me. I think the harder part of this issue will be identifying which sets to freeze

[Endle]

I found an interesting case after my first glance (I'm not sure it if's related to this issue)
See this code

def f():
    a = (1, 2, 3)
    b = (1, 2, 3)
    c = tuple(1, 2, 3)

We know a, b, c are identical. However, cython result is

 * def f():
 *     a = (1, 2, 3)             # <<<<<<<<<<<<<<
 *     b = (1, 2, 3)
 *     c = tuple(1, 2, 3)
 */
  __Pyx_INCREF(__pyx_tuple_);
  __pyx_v_a = __pyx_tuple_;

  /* "tuple.pyx":3
 * def f():
 *     a = (1, 2, 3)
 *     b = (1, 2, 3)             # <<<<<<<<<<<<<<
 *     c = tuple(1, 2, 3)
 * 
 */
  __Pyx_INCREF(__pyx_tuple_);
  __pyx_v_b = __pyx_tuple_;

  /* "tuple.pyx":4
 *     a = (1, 2, 3)
 *     b = (1, 2, 3)
 *     c = tuple(1, 2, 3)             # <<<<<<<<<<<<<<
 * 
 * #a = {1, 2, 3}
 */
  __pyx_t_1 = __Pyx_PyObject_Call(((PyObject *)(&PyTuple_Type)), __pyx_tuple_, NULL); if (unlikely(!__pyx_t_1)) __PYX_ERR(0, 4, __pyx_L1_error)
  __Pyx_GOTREF(__pyx_t_1);
  __pyx_v_c = ((PyObject*)__pyx_t_1);
  __pyx_t_1 = 0;

It's making an extra function call. The tuple keyword will be considered as
<Cython.Compiler.ExprNodes.SimpleCallNode object at 0x7f15633615e0>

For frozenset, I think the logic lies in _handle_simple_function_frozenset and I would have a deeper look at it

Thank you

Edit: I mean OptimizeBuiltinCalls._handle_simple_function_frozenset

[scoder]

tuple(1, 2, 3)

Gives me a TypeError at runtime, too many arguments. Same in Cython.

[Endle]

tuple(1, 2, 3)

Gives me a TypeError at runtime, too many arguments. Same in Cython.

Sorry, my bad.

  /* "tuple.pyx":4
 *     a = (1, 2, 3)
 *     b = (1, 2, 3)
 *     c = tuple((1, 2, 3))             # <<<<<<<<<<<<<<
 * 
 * #a = {1, 2, 3}
 */
  __Pyx_INCREF(__pyx_tuple_);
  __pyx_v_c = __pyx_tuple_;

If I create a tuple correctly, cython will re-use the same tuple object as expected.

[Endle]

I created a draft at Endle#1

With some ugly hacks, I could let cython share the same frozenset object

/* #### Code section: cached_constants ### */

static CYTHON_SMALL_CODE int __Pyx_InitCachedConstants(void) {
  __Pyx_RefNannyDeclarations
  __Pyx_RefNannySetupContext("__Pyx_InitCachedConstants", 0);

  /* "set3.pyx":2
 * a = set((4, 5))
 * b = frozenset((4, 5, 6))             # <<<<<<<<<<<<<<
 * c = frozenset((4, 5, 6))
 * print(b)
 */
  __pyx_tuple__2 = PyTuple_Pack(3, __pyx_int_4, __pyx_int_5, __pyx_int_6); if (unlikely(!__pyx_tuple__2)) __PYX_ERR(0, 2, __pyx_L1_error)
  __Pyx_GOTREF(__pyx_tuple__2);
  __Pyx_GIVEREF(__pyx_tuple__2);
  __pyx_frozenset_ = PyFrozenSet_New(__pyx_tuple__2); if (unlikely(!__pyx_frozenset_)) __PYX_ERR(0, 2, __pyx_L1_error)
  __Pyx_GOTREF(__pyx_frozenset_);
  __Pyx_RefNannyFinishContext();
  return 0;
  __pyx_L1_error:;
  __Pyx_RefNannyFinishContext();
  return -1;
}

Then

  /* "set3.pyx":2
 * a = set((4, 5))
 * b = frozenset((4, 5, 6))             # <<<<<<<<<<<<<<
 * c = frozenset((4, 5, 6))
 * print(b)
 */
  if (PyDict_SetItem(__pyx_d, __pyx_n_s_b, __pyx_frozenset_) < 0) __PYX_ERR(0, 2, __pyx_L1_error)

  /* "set3.pyx":3
 * a = set((4, 5))
 * b = frozenset((4, 5, 6))
 * c = frozenset((4, 5, 6))             # <<<<<<<<<<<<<<
 * print(b)
 * print(c)
 */
  if (PyDict_SetItem(__pyx_d, __pyx_n_s_c, __pyx_frozenset_) < 0) __PYX_ERR(0, 3, __pyx_L1_error)

[Endle]

I need some time to understand ref and other code generation components to clean up my PR