#37899

Committed 10 Sep 2024 06:39AM UTC coverage: 87.749% (-0.009%) from 87.758%

Build # #37899

Build Type

push

local

Committed by

web-flow

Commit Message

Avoid materializing arrays in bidiag matmul (#55450)

Currently, small `Bidiagonal`/`Tridiagonal` matrices are materialized in
matrix multiplications, but this is wasteful and unnecessary. This PR
changes this to use a naive matrix multiplication for small matrices,
and fall back to the banded multiplication for larger ones.
Multiplication by a `Bidiagonal` falls back to a banded matrix
multiplication for all sizes in the current implementation, and iterates
in a cache-friendly manner for the non-`Bidiagonal` matrix.

In certain cases, the matrices were being materialized if the
non-structured matrix was small, even if the structured matrix was
large. This is changed as well in this PR.

Some improvements in performance:
```julia
julia> B = Bidiagonal(rand(3), rand(2), :U); A = rand(size(B)...); C = similar(A);

julia> @btime mul!($C, $A, $B);
  193.152 ns (6 allocations: 352 bytes) # nightly v"1.12.0-DEV.1034"
  18.826 ns (0 allocations: 0 bytes) # This PR

julia> T = Tridiagonal(rand(99), rand(100), rand(99)); A = rand(2, size(T,2)); C = similar(A);

julia> @btime mul!($C, $A, $T);
  9.398 μs (8 allocations: 79.94 KiB) # nightly
  416.407 ns (0 allocations: 0 bytes) # This PR

julia> B = Bidiagonal(rand(300), rand(299), :U); A = rand(20000, size(B,2)); C = similar(A);

julia> @btime mul!($C, $A, $B);
  33.395 ms (0 allocations: 0 bytes) # nightly
  6.695 ms (0 allocations: 0 bytes) # This PR (cache-friendly)
```

Closes https://github.com/JuliaLang/julia/pull/55414

---------

Co-authored-by: Daniel Karrasch <daniel.karrasch@posteo.de>

Run Details

241 of 241 new or added lines in 2 files covered. (100.0%)

394 existing lines in 11 files now uncovered.

78456 of 89410 relevant lines covered (87.75%)

16601480.8 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

91.67

/stdlib/Markdown/src/parse/util.jl

# This file is a part of Julia. License is MIT: https://julialang.org/license

macro dotimes(n, body)
    quote
        for i = 1:$(esc(n))
            $(esc(body))
        end
    end
end

const whitespace = " \t\r"

"""
Skip any leading whitespace. Returns io.
"""
function skipwhitespace(io::IO; newlines = true)
    while !eof(io) && (peek(io, Char) in whitespace || (newlines && peek(io) == UInt8('\n')))
        read(io, Char)
    end
    return io
end

"""
Skip any leading blank lines. Returns the number skipped.
"""
function skipblank(io::IO)
    start = position(io)
    i = 0
    for c in readeach(io, Char)
        c == '\n' && (start = position(io); i+=1; continue)
        c == '\r' && (start = position(io); i+=1; continue)
        c in whitespace || break
    end
    seek(io, start)
    return i
end

"""
Return true if the line contains only (and, unless allowempty,
at least one of) the characters given.
"""
function linecontains(io::IO, chars; allow_whitespace = true,
                                     eat = true,
                                     allowempty = false)
    start = position(io)
    l = readline(io)
    length(l) == 0 && return allowempty

    result = allowempty
    for c in l
        c in whitespace && (allow_whitespace ? continue : (result = false; break))
        c in chars && (result = true; continue)
        result = false; break
    end
    !(result && eat) && seek(io, start)
    return result
end

blankline(io::IO; eat = true) =
    linecontains(io, "",
                 allow_whitespace = true,
                 allowempty = true,
                 eat = eat)

"""
Test if the stream starts with the given string.
`eat` specifies whether to advance on success (true by default).
`padding` specifies whether leading whitespace should be ignored.
"""
function startswith(stream::IO, s::AbstractString; eat = true, padding = false, newlines = true)
    start = position(stream)
    padding && skipwhitespace(stream, newlines = newlines)
    result = true
    for char in s
        !eof(stream) && read(stream, Char) == char ||
            (result = false; break)
    end
    !(result && eat) && seek(stream, start)
    return result
end

function startswith(stream::IO, c::AbstractChar; eat = true)
    if !eof(stream) && peek(stream) == UInt8(c)
        eat && read(stream, Char)
        return true
    else
        return false
    end
end

function startswith(stream::IO, ss::Vector{<:AbstractString}; kws...)
    any(s->startswith(stream, s; kws...), ss)
end

function startswith(stream::IO, r::Regex; eat = true, padding = false)
    @assert Base.startswith(r.pattern, "^")
    start = position(stream)
    padding && skipwhitespace(stream)
    line = readline(stream)
    seek(stream, start)
    m = match(r, line)
    m === nothing && return ""
    eat && @dotimes length(m.match) read(stream, Char)
    return m.match
end

"""
Executes the block of code, and if the return value is `nothing`,
returns the stream to its initial position.
"""
function withstream(f, stream)
    pos = position(stream)
    result = f()
    (result ≡ nothing || result ≡ false) && seek(stream, pos)
    return result
end

"""
Consume the standard allowed markdown indent of
three spaces. Returns false if there are more than
three present.
"""
function eatindent(io::IO, n = 3)
    withstream(io) do
        m = 0
        while startswith(io, ' ') m += 1 end
        return m <= n
    end
end

"""
Read the stream until startswith(stream, delim)
The delimiter is consumed but not included.
Returns nothing and resets the stream if delim is
not found.
"""
function readuntil(stream::IO, delimiter; newlines = false, match = nothing)
    withstream(stream) do
        buffer = IOBuffer()
        count = 0
        while !eof(stream)
            if startswith(stream, delimiter)
                if count == 0
                    return String(take!(buffer))
                else
                    count -= 1
                    write(buffer, delimiter)
                    continue
                end
            end
            char = read(stream, Char)
            char == match && (count += 1)
            !newlines && char == '\n' && break
            write(buffer, char)
        end
    end
end

# TODO: refactor this. If we're going to assume
# the delimiter is a single character + a minimum
# repeat we may as well just pass that into the
# function.

"""
Parse a symmetrical delimiter which wraps words.
i.e. `*word word*` but not `*word * word`.
`repeat` specifies whether the delimiter can be repeated.
Escaped delimiters are not yet supported.
"""
function parse_inline_wrapper(stream::IO, delimiter::AbstractString; rep = false)
    delimiter, nmin = string(delimiter[1]), length(delimiter)
    withstream(stream) do
        if position(stream) >= 1
            # check the previous byte isn't a delimiter
            skip(stream, -1)
            (read(stream, Char) in delimiter) && return nothing
        end
        n = nmin
        startswith(stream, delimiter^n) || return nothing
        while startswith(stream, delimiter); n += 1; end
        !rep && n > nmin && return nothing
        !eof(stream) && peek(stream, Char) in whitespace && return nothing

        buffer = IOBuffer()
        for char in readeach(stream, Char)
            write(buffer, char)
            if !(char in whitespace || char == '\n' || char in delimiter) && startswith(stream, delimiter^n)
                trailing = 0
                while startswith(stream, delimiter); trailing += 1; end
                trailing == 0 && return String(take!(buffer))
                write(buffer, delimiter ^ (n + trailing))
            end
        end
    end
end

function showrest(io::IO)
    start = position(io)
    show(read(io, String))
    println()
    seek(io, start)
end

1	# This file is a part of Julia. License is MIT: https://julialang.org/license
2
3	macro dotimes(n, body)
4	quote
5	for i = 1:$(esc(n))	39,617✔
6	$(esc(body))	43,673✔
7	end	47,729✔
8	end
9	end
10
11	const whitespace = " \t\r"
12
13	"""
14	Skip any leading whitespace. Returns io.
15	"""
16	function skipwhitespace(io::IO; newlines = true)	213,582✔
17	while !eof(io) && (peek(io, Char) in whitespace \|\| (newlines && peek(io) == UInt8('\n')))	264,836✔
18	read(io, Char)	51,271✔
19	end	51,271✔
20	return io	106,791✔
21	end
22
23	"""
24	Skip any leading blank lines. Returns the number skipped.
25	"""
26	function skipblank(io::IO)	71,334✔
27	start = position(io)	71,334✔
UNCOV 28	i = 0	×
29	for c in readeach(io, Char)	134,645✔
30	c == '\n' && (start = position(io); i+=1; continue)	91,209✔
31	c == '\r' && (start = position(io); i+=1; continue)	87,174✔
32	c in whitespace \|\| break	87,173✔
33	end	57,971✔
34	seek(io, start)	142,668✔
35	return i	71,334✔
36	end
37
38	"""
39	Return true if the line contains only (and, unless allowempty,
40	at least one of) the characters given.
41	"""
42	function linecontains(io::IO, chars; allow_whitespace = true,	122,264✔
43	eat = true,
44	allowempty = false)
45	start = position(io)	61,132✔
46	l = readline(io)	61,132✔
47	length(l) == 0 && return allowempty	61,132✔
48
UNCOV 49	result = allowempty	×
50	for c in l	78,708✔
51	c in whitespace && (allow_whitespace ? continue : (result = false; break))	40,310✔
52	c in chars && (result = true; continue)	39,352✔
53	result = false; break	39,352✔
54	end	1,906✔
55	!(result && eat) && seek(io, start)	78,708✔
56	return result	39,356✔
57	end
58
59	blankline(io::IO; eat = true) =	122,264✔
60	linecontains(io, "",
61	allow_whitespace = true,
62	allowempty = true,
63	eat = eat)
64
65	"""
66	Test if the stream starts with the given string.
67	`eat` specifies whether to advance on success (true by default).
68	`padding` specifies whether leading whitespace should be ignored.
69	"""
70	function startswith(stream::IO, s::AbstractString; eat = true, padding = false, newlines = true)	1,202,966✔
71	start = position(stream)	601,483✔
72	padding && skipwhitespace(stream, newlines = newlines)	601,483✔
73	result = true	3,484✔
74	for char in s	1,202,966✔
75	!eof(stream) && read(stream, Char) == char \|\|	658,777✔
76	(result = false; break)	3,212✔
77	end	172,212✔
78	!(result && eat) && seek(stream, start)	1,145,342✔
79	return result	601,483✔
80	end
81
82	function startswith(stream::IO, c::AbstractChar; eat = true)	419,305✔
83	if !eof(stream) && peek(stream) == UInt8(c)	418,718✔
84	eat && read(stream, Char)	81,804✔
85	return true	81,804✔
86	else
87	return false	336,914✔
88	end
89	end
90
91	function startswith(stream::IO, ss::Vector{<:AbstractString}; kws...)	×
92	any(s->startswith(stream, s; kws...), ss)	×
93	end
94
95	function startswith(stream::IO, r::Regex; eat = true, padding = false)	210,230✔
96	@assert Base.startswith(r.pattern, "^")	105,115✔
97	start = position(stream)	105,115✔
98	padding && skipwhitespace(stream)	105,115✔
99	line = readline(stream)	105,115✔
100	seek(stream, start)	210,230✔
101	m = match(r, line)	105,115✔
102	m === nothing && return ""	105,115✔
103	eat && @dotimes length(m.match) read(stream, Char)	40,207✔
104	return m.match	40,207✔
105	end
106
107	"""
108	Executes the block of code, and if the return value is `nothing`,
109	returns the stream to its initial position.
110	"""
111	function withstream(f, stream)	43,374✔
112	pos = position(stream)	593,366✔
113	result = f()	593,392✔
114	(result ≡ nothing \|\| result ≡ false) && seek(stream, pos)	973,582✔
115	return result	593,366✔
116	end
117
118	"""
119	Consume the standard allowed markdown indent of
120	three spaces. Returns false if there are more than
121	three present.
122	"""
123	function eatindent(io::IO, n = 3)
124	withstream(io) do	256,654✔
125	m = 0	115,899✔
126	while startswith(io, ' ') m += 1 end	167,709✔
127	return m <= n	115,899✔
128	end
129	end
130
131	"""
132	Read the stream until startswith(stream, delim)
133	The delimiter is consumed but not included.
134	Returns nothing and resets the stream if delim is
135	not found.
136	"""
137	function readuntil(stream::IO, delimiter; newlines = false, match = nothing)	51,196✔
138	withstream(stream) do	51,196✔
139	buffer = IOBuffer()	51,040✔
140	count = 0	13,815✔
141	while !eof(stream)	470,543✔
142	if startswith(stream, delimiter)	470,387✔
143	if count == 0	13,746✔
144	return String(take!(buffer))	50,884✔
145	else
146	count -= 1	61✔
147	write(buffer, delimiter)	61✔
148	continue	61✔
149	end
150	end
151	char = read(stream, Char)	419,442✔
152	char == match && (count += 1)	129,529✔
153	!newlines && char == '\n' && break	419,442✔
154	write(buffer, char)	419,442✔
155	end	419,503✔
156	end
157	end
158
159	# TODO: refactor this. If we're going to assume
160	# the delimiter is a single character + a minimum
161	# repeat we may as well just pass that into the
162	# function.
163
164	"""
165	Parse a symmetrical delimiter which wraps words.
166	i.e. `word word` but not `word word`.
167	`repeat` specifies whether the delimiter can be repeated.
168	Escaped delimiters are not yet supported.
169	"""
170	function parse_inline_wrapper(stream::IO, delimiter::AbstractString; rep = false)	45,392✔
171	delimiter, nmin = string(delimiter[1]), length(delimiter)	45,392✔
172	withstream(stream) do	22,696✔
173	if position(stream) >= 1	22,696✔
174	# check the previous byte isn't a delimiter
175	skip(stream, -1)	24,926✔
176	(read(stream, Char) in delimiter) && return nothing	12,463✔
177	end
178	n = nmin	22,688✔
179	startswith(stream, delimiter^n) \|\| return nothing	44,818✔
180	while startswith(stream, delimiter); n += 1; end	565✔
181	!rep && n > nmin && return nothing	558✔
182	!eof(stream) && peek(stream, Char) in whitespace && return nothing	554✔
183
184	buffer = IOBuffer()	542✔
185	for char in readeach(stream, Char)	1,084✔
186	write(buffer, char)	8,223✔
187	if !(char in whitespace \|\| char == '\n' \|\| char in delimiter) && startswith(stream, delimiter^n)	15,648✔
188	trailing = 0	5✔
189	while startswith(stream, delimiter); trailing += 1; end	399✔
190	trailing == 0 && return String(take!(buffer))	395✔
191	write(buffer, delimiter ^ (n + trailing))	4✔
192	end
193	end	7,832✔
194	end
195	end
196
197	function showrest(io::IO)	×
198	start = position(io)	×
199	show(read(io, String))	×
200	println()	×
201	seek(io, start)	×
202	end

JuliaLang / julia / #37899

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous