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

Jump to bottom

Why don't Pow and Div have hash field? #465

Open
bowenszhu opened this issue Aug 26, 2022 · 0 comments · May be fixed by #590
Open

Why don't Pow and Div have hash field? #465

bowenszhu opened this issue Aug 26, 2022 · 0 comments · May be fixed by #590

Comments

@bowenszhu
Copy link
Member

bowenszhu commented Aug 26, 2022 •
edited
Loading

SymbolicUtils.jl/src/types.jl

Lines 51 to 61 in dcbe861

struct Div{T} <: BasicSymbolic{T}
num::Any = 1
den::Any = 1
simplified::Bool = false
arguments::Vector{Any} = EMPTY_ARGS
end
struct Pow{T} <: BasicSymbolic{T}
base::Any = 1
exp::Any = 1
arguments::Vector{Any} = EMPTY_ARGS
end

SymbolicUtils.jl/src/types.jl

Lines 228 to 256 in dcbe861

function Base.hash(s::BasicSymbolic, salt::UInt)
E = exprtype(s)
if E === SYM
hash(nameof(s), salt ⊻ 0x4de7d7c66d41da43)
elseif E === ADD || E === MUL
!iszero(salt) && return hash(hash(s, zero(UInt64)), salt)
h = s.hash[]
!iszero(h) && return h
hashoffset = isadd(s) ? 0xaddaddaddaddadda : 0xaaaaaaaaaaaaaaaa
h′= hash(hashoffset, hash(s.coeff, hash(s.dict, salt)))
s.hash[] = h′
return h′
elseif E === DIV
return hash(s.num, hash(s.den, salt ⊻ 0x334b218e73bbba53))
elseif E === POW
hash(s.exp, hash(s.base, salt ⊻ 0x2b55b97a6efb080c))
elseif E === TERM
!iszero(salt) && return hash(hash(s, zero(UInt)), salt)
h = s.hash[]
!iszero(h) && return h
op = operation(s)
oph = op isa Function ? nameof(op) : op
h′ = hashvec(arguments(s), hash(oph, salt))
s.hash[] = h′
return h′
else
error_on_type()
end
end

For Add, Mul and Term, once hash() is called, the field hash is filled and then it doesn't need to recompute the hash down to the subtree when hash() is called later.

But Sym, Pow and Div don't share this benefit.

It would be inefficient for, for example, the following expression.

(((((a / b) ^ c) / d) ^ e) / f) ^ g
@bowenszhu bowenszhu changed the title Why Pow and Div do not have hash field? Why don't Pow and Div have hash field? Aug 26, 2022
@bowenszhu bowenszhu linked a pull request Apr 30, 2024 that will close this issue
Open
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

Add hash field to all BasicSymbolic subtypes JuliaSymbolics/SymbolicUtils.jl
1 participant
@bowenszhu