Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

[mypyc] Fast tuple equality checks #9343

Merged
merged 12 commits into from
Aug 27, 2020
Merged

[mypyc] Fast tuple equality checks #9343

Show file tree
Hide file tree
Changes from 10 commits
Commits
Show all changes
12 commits
Select commit Hold shift + click to select a range
91ce611
initial implementation of fast tuple equality checks
TH3CHARLie Aug 23, 2020
e3f55e3
handle empty tuples
TH3CHARLie Aug 23, 2020
b50712c
fix block initialization bug
TH3CHARLie Aug 23, 2020
b13208a
change special case position to support nested tuples
TH3CHARLie Aug 23, 2020
7ce1896
add cast to bool if necessary
TH3CHARLie Aug 24, 2020
e34c025
fix typo
TH3CHARLie Aug 24, 2020
60a809c
remove same type check
TH3CHARLie Aug 25, 2020
8037df1
fix
TH3CHARLie Aug 25, 2020
3179cf1
fix != bug
TH3CHARLie Aug 25, 2020
1f859da
specialize empty tuples
TH3CHARLie Aug 25, 2020
47e8be3
use bool_op instead of coerce
TH3CHARLie Aug 26, 2020
7657f7a
Merge branch 'master' into tuple-equality
TH3CHARLie Aug 26, 2020
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
3 changes: 3 additions & 0 deletions mypyc/irbuild/builder.py
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -254,6 +254,9 @@ def binary_int_op(self, type: RType, lhs: Value, rhs: Value, op: int, line: int)
def compare_tagged(self, lhs: Value, rhs: Value, op: str, line: int) -> Value:
return self.builder.compare_tagged(lhs, rhs, op, line)

def compare_tuples(self, lhs: Value, rhs: Value, op: str, line: int) -> Value:
return self.builder.compare_tuples(lhs, rhs, op, line)

def builtin_len(self, val: Value, line: int) -> Value:
return self.builder.builtin_len(val, line)

Expand Down
58 changes: 56 additions & 2 deletions mypyc/irbuild/ll_builder.py
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -22,14 +22,14 @@
LoadStatic, MethodCall, PrimitiveOp, OpDescription, RegisterOp, CallC, Truncate,
RaiseStandardError, Unreachable, LoadErrorValue, LoadGlobal,
NAMESPACE_TYPE, NAMESPACE_MODULE, NAMESPACE_STATIC, BinaryIntOp, GetElementPtr,
LoadMem, ComparisonOp, LoadAddress
LoadMem, ComparisonOp, LoadAddress, TupleGet
)
from mypyc.ir.rtypes import (
RType, RUnion, RInstance, optional_value_type, int_rprimitive, float_rprimitive,
bool_rprimitive, list_rprimitive, str_rprimitive, is_none_rprimitive, object_rprimitive,
c_pyssize_t_rprimitive, is_short_int_rprimitive, is_tagged, PyVarObject, short_int_rprimitive,
is_list_rprimitive, is_tuple_rprimitive, is_dict_rprimitive, is_set_rprimitive, PySetObject,
none_rprimitive
none_rprimitive, RTuple, is_bool_rprimitive
)
from mypyc.ir.func_ir import FuncDecl, FuncSignature
from mypyc.ir.class_ir import ClassIR, all_concrete_classes
Expand Down Expand Up @@ -552,6 +552,10 @@ def binary_op(self,
rreg: Value,
expr_op: str,
line: int) -> Value:
# special case tuple comparison here so that nested tuples can be supported
if (isinstance(lreg.type, RTuple) and isinstance(rreg.type, RTuple)
and expr_op in ('==', '!=')):
return self.compare_tuples(lreg, rreg, expr_op, line)
# Special case == and != when we can resolve the method call statically.
value = None
if expr_op in ('==', '!='):
Expand Down Expand Up @@ -622,6 +626,56 @@ def compare_tagged(self, lhs: Value, rhs: Value, op: str, line: int) -> Value:
self.goto_and_activate(out)
return result

def compare_tuples(self,
lhs: Value,
rhs: Value,
op: str,
line: int = -1) -> Value:
"""Compare two tuples item by item"""
# type cast to pass mypy check
assert isinstance(lhs.type, RTuple) and isinstance(rhs.type, RTuple)
equal = True if op == '==' else False
result = self.alloc_temp(bool_rprimitive)
# empty tuples
if len(lhs.type.types) == 0 and len(rhs.type.types) == 0:
self.add(Assign(result, self.true() if equal else self.false(), line))
return result
length = len(lhs.type.types)
false_assign, true_assign, out = BasicBlock(), BasicBlock(), BasicBlock()
check_blocks = [BasicBlock() for i in range(length)]
lhs_items = [self.add(TupleGet(lhs, i, line)) for i in range(length)]
rhs_items = [self.add(TupleGet(rhs, i, line)) for i in range(length)]

if equal:
early_stop, final = false_assign, true_assign
else:
early_stop, final = true_assign, false_assign

for i in range(len(lhs.type.types)):
if i != 0:
self.activate_block(check_blocks[i])
lhs_item = lhs_items[i]
rhs_item = rhs_items[i]
compare = self.binary_op(lhs_item, rhs_item, op, line)
# Cast to bool if necessary since most types uses comparison returning a object type
# See generic_ops.py for more information
if not is_bool_rprimitive(compare.type):
compare = self.coerce(compare, bool_rprimitive, line)
Copy link
Collaborator

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Coerce only does a type check. I think that the normal CPython semantics would be to allow arbitrary objects that have a truth value, i.e. it may be better to use bool_op instead. Consider what happens if a user-defined class defines __eq__ that returns a non-bool value such as 1 or 'x'.

if i < len(lhs.type.types) - 1:
branch = Branch(compare, early_stop, check_blocks[i + 1], Branch.BOOL_EXPR)
else:
branch = Branch(compare, early_stop, final, Branch.BOOL_EXPR)
# if op is ==, we branch on false, else branch on true
branch.negated = equal
self.add(branch)
self.activate_block(false_assign)
self.add(Assign(result, self.false(), line))
self.goto(out)
self.activate_block(true_assign)
self.add(Assign(result, self.true(), line))
self.goto_and_activate(out)
return result

def unary_op(self,
lreg: Value,
expr_op: str,
Expand Down