#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

85.96

/stdlib/Markdown/src/GitHub/table.jl

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

mutable struct Table
    rows::Vector{Vector{Any}}
    align::Vector{Symbol}
end

function parserow(stream::IO)
    withstream(stream) do
        line = readline(stream)
        row = split(line, r"(?<!\\)\|")
        length(row) == 1 && return
        isempty(row[1]) && popfirst!(row)
        map!(x -> strip(replace(x, "\\|" => "|")), row, row)
        isempty(row[end]) && pop!(row)
        return row
    end
end

function rowlength!(row, len)
    while length(row) < len push!(row, "") end
    while length(row) > len pop!(row) end
    return row
end

const default_align = :r

function parsealign(row)
    align = Symbol[]
    for s in row
        (length(s) ≥ 3 && s ⊆ Set("-:")) || return
        push!(align,
              s[1] == ':' ? (s[end] == ':' ? :c : :l) :
              s[end] == ':' ? :r :
              default_align)
    end
    return align
end

function github_table(stream::IO, md::MD)
    withstream(stream) do
        skipblank(stream)
        rows = []
        cols = 0
        align = nothing
        while (row = parserow(stream)) !== nothing
            if length(rows) == 0
                cols = length(row)
            end
            if align === nothing && length(rows) == 1 # Must have a --- row
                align = parsealign(row)
                (align === nothing || length(align) != cols) && return false
            else
                push!(rows, map(x -> parseinline(x, md), rowlength!(row, cols)))
            end
        end
        length(rows) <= 1 && return false
        push!(md, Table(rows, align))
        return true
    end
end

function html(io::IO, md::Table)
    withtag(io, :table) do
        for (i, row) in enumerate(md.rows)
            withtag(io, :tr) do
                for (j, c) in enumerate(md.rows[i])
                    alignment = md.align[j]
                    alignment = alignment === :l ? "left" : alignment === :r ? "right" : "center"
                     withtag(io, i == 1 ? :th : :td, ("align", alignment)) do
                        htmlinline(io, c)
                    end
                end
            end
        end
    end
end

mapmap(f, xss) = map(xs->map(f, xs), xss)

colwidths(rows; len = length, min = 0) =
    reduce((x,y) -> max.(x,y), [min; convert(Vector{Vector{Int}}, mapmap(len, rows))])

padding(width, twidth, a) =
    a === :l ? (0, twidth - width) :
    a === :r ? (twidth - width, 0) :
    a === :c ? (floor(Int, (twidth-width)/2), ceil(Int, (twidth-width)/2)) :
    error("Invalid alignment $a")

function padcells!(rows, align; len = length, min = 0)
    widths = colwidths(rows, len = len, min = min)
    for i = 1:length(rows), j = axes(rows[1],1)
        cell = rows[i][j]
        lpad, rpad = padding(len(cell), widths[j], align[j])
        rows[i][j] = " "^lpad * cell * " "^rpad
    end
    return rows
end

_dash(width, align) =
    align === :l ? ":" * "-"^width * " " :
    align === :r ? " " * "-"^width * ":" :
    align === :c ? ":" * "-"^width * ":" :
    throw(ArgumentError("Invalid alignment $align"))

function plain(io::IO, md::Table)
    cells = mapmap(md.rows) do each
        replace(plaininline(each), "|" => "\\|")
    end
    padcells!(cells, md.align, len = length, min = 3)
    for i = axes(cells,1)
        print(io, "| ")
        join(io, cells[i], " | ")
        println(io, " |")
        if i == 1
            print(io, "|")
            join(io, [_dash(length(cells[i][j]), md.align[j]) for j = axes(cells[1],1)], "|")
            println(io, "|")
        end
    end
end

function rst(io::IO, md::Table)
    cells = mapmap(rstinline, md.rows)
    padcells!(cells, md.align, len = length, min = 3)
    single = ["-"^length(c) for c in cells[1]]
    double = ["="^length(c) for c in cells[1]]
    function print_row(row, row_sep, col_sep)
        print(io, col_sep, row_sep)
        join(io, row, string(row_sep, col_sep, row_sep))
        println(io, row_sep, col_sep)
    end
    print_row(single, '-', '+')
    for i = 1:length(cells)
        print_row(cells[i], ' ', '|')
        i ≡ 1 ? print_row(double, '=', '+') :
                print_row(single, '-', '+')
    end
end

function term(io::IO, md::Table, columns)
    margin_str = " "^margin
    cells = mapmap(x -> annotprint(terminline, x), md.rows)
    padcells!(cells, md.align, len = textwidth)
    for i = 1:length(cells)
        print(io, margin_str)
        join(io, cells[i], " ")
        if i == 1
            println(io)
            print(io, margin_str)
            join(io, ["–"^textwidth(cells[i][j]) for j = 1:length(cells[1])], " ")
        end
        i < length(cells) && println(io)
    end
end

function latex(io::IO, md::Table)
    wrapblock(io, "tabular") do
        align = md.align
        println(io, "{$(join(align, " | "))}")
        for (i, row) in enumerate(md.rows)
            for (j, cell) in enumerate(row)
                j != 1 && print(io, " & ")
                latexinline(io, cell)
            end
            println(io, " \\\\")
            if i == 1
                println(io, "\\hline")
            end
        end
    end
end

1	# This file is a part of Julia. License is MIT: https://julialang.org/license
2
3	mutable struct Table
4	rows::Vector{Vector{Any}}	99✔
5	align::Vector{Symbol}
6	end
7
8	function parserow(stream::IO)
9	withstream(stream) do	31,212✔
10	line = readline(stream)	15,752✔
11	row = split(line, r"(?<!\\)\\|")	15,752✔
12	length(row) == 1 && return	15,752✔
13	isempty(row[1]) && popfirst!(row)	292✔
14	map!(x -> strip(replace(x, "\\\|" => "\|")), row, row)	1,972✔
15	isempty(row[end]) && pop!(row)	292✔
16	return row	292✔
17	end
18	end
19
20	function rowlength!(row, len)	253✔
21	while length(row) < len push!(row, "") end	253✔
22	while length(row) > len pop!(row) end	253✔
23	return row	253✔
24	end
25
26	const default_align = :r
27
28	function parsealign(row)	39✔
29	align = Symbol[]	39✔
30	for s in row	39✔
31	(length(s) ≥ 3 && s ⊆ Set("-:")) \|\| return	92✔
32	push!(align,	165✔
33	s[1] == ':' ? (s[end] == ':' ? :c : :l) :
34	s[end] == ':' ? :r :
35	default_align)
36	end	92✔
37	return align	39✔
38	end
39
40	function github_table(stream::IO, md::MD)	15,460✔
41	withstream(stream) do	15,460✔
42	skipblank(stream)	15,460✔
43	rows = []	15,460✔
UNCOV 44	cols = 0	×
UNCOV 45	align = nothing	×
46	while (row = parserow(stream)) !== nothing	31,212✔
47	if length(rows) == 0	292✔
48	cols = length(row)	77✔
49	end
50	if align === nothing && length(rows) == 1 # Must have a --- row	292✔
51	align = parsealign(row)	39✔
52	(align === nothing \|\| length(align) != cols) && return false	39✔
53	else
54	push!(rows, map(x -> parseinline(x, md), rowlength!(row, cols)))	905✔
55	end
56	end	292✔
57	length(rows) <= 1 && return false	15,460✔
58	push!(md, Table(rows, align))	78✔
59	return true	39✔
60	end
61	end
62
63	function html(io::IO, md::Table)	10✔
64	withtag(io, :table) do	10✔
65	for (i, row) in enumerate(md.rows)	20✔
66	withtag(io, :tr) do	21✔
67	for (j, c) in enumerate(md.rows[i])	21✔
68	alignment = md.align[j]	49✔
69	alignment = alignment === :l ? "left" : alignment === :r ? "right" : "center"	81✔
70	withtag(io, i == 1 ? :th : :td, ("align", alignment)) do	49✔
71	htmlinline(io, c)	49✔
72	end
73	end	49✔
74	end
75	end	32✔
76	end
77	end
78
79	mapmap(f, xss) = map(xs->map(f, xs), xss)	174✔
80
81	colwidths(rows; len = length, min = 0) =	30✔
82	reduce((x,y) -> max.(x,y), [min; convert(Vector{Vector{Int}}, mapmap(len, rows))])	72✔
83
84	padding(width, twidth, a) =	198✔
85	a === :l ? (0, twidth - width) :
86	a === :r ? (twidth - width, 0) :
87	a === :c ? (floor(Int, (twidth-width)/2), ceil(Int, (twidth-width)/2)) :
88	error("Invalid alignment $a")
89
90	function padcells!(rows, align; len = length, min = 0)	30✔
91	widths = colwidths(rows, len = len, min = min)	15✔
92	for i = 1:length(rows), j = axes(rows[1],1)	15✔
93	cell = rows[i][j]	198✔
94	lpad, rpad = padding(len(cell), widths[j], align[j])	198✔
95	rows[i][j] = " "^lpad * cell * " "^rpad	198✔
96	end	255✔
97	return rows	15✔
98	end
99
100	_dash(width, align) =	31✔
101	align === :l ? ":" * "-"^width * " " :
102	align === :r ? " " * "-"^width * ":" :
103	align === :c ? ":" * "-"^width * ":" :
104	throw(ArgumentError("Invalid alignment $align"))
105
106	function plain(io::IO, md::Table)	11✔
107	cells = mapmap(md.rows) do each	11✔
108	replace(plaininline(each), "\|" => "\\\|")	188✔
109	end
110	padcells!(cells, md.align, len = length, min = 3)	11✔
111	for i = axes(cells,1)	11✔
112	print(io, "\| ")	64✔
113	join(io, cells[i], " \| ")	64✔
114	println(io, " \|")	64✔
115	if i == 1	64✔
116	print(io, "\|")	11✔
117	join(io, [_dash(length(cells[i][j]), md.align[j]) for j = axes(cells[1],1)], "\|")	11✔
118	println(io, "\|")	11✔
119	end
120	end	64✔
121	end
122
123	function rst(io::IO, md::Table)	×
124	cells = mapmap(rstinline, md.rows)	×
125	padcells!(cells, md.align, len = length, min = 3)	×
126	single = ["-"^length(c) for c in cells[1]]	×
127	double = ["="^length(c) for c in cells[1]]	×
128	function print_row(row, row_sep, col_sep)	×
129	print(io, col_sep, row_sep)	×
130	join(io, row, string(row_sep, col_sep, row_sep))	×
131	println(io, row_sep, col_sep)	×
132	end
133	print_row(single, '-', '+')	×
134	for i = 1:length(cells)	×
135	print_row(cells[i], ' ', '\|')	×
136	i ≡ 1 ? print_row(double, '=', '+') :	×
137	print_row(single, '-', '+')
138	end	×
139	end
140
141	function term(io::IO, md::Table, columns)	4✔
142	margin_str = " "^margin	4✔
143	cells = mapmap(x -> annotprint(terminline, x), md.rows)	14✔
144	padcells!(cells, md.align, len = textwidth)	4✔
145	for i = 1:length(cells)	4✔
146	print(io, margin_str)	8✔
147	join(io, cells[i], " ")	8✔
148	if i == 1	8✔
149	println(io)	4✔
150	print(io, margin_str)	4✔
151	join(io, ["–"^textwidth(cells[i][j]) for j = 1:length(cells[1])], " ")	4✔
152	end
153	i < length(cells) && println(io)	8✔
154	end	8✔
155	end
156
157	function latex(io::IO, md::Table)	1✔
158	wrapblock(io, "tabular") do	1✔
159	align = md.align	1✔
160	println(io, "{$(join(align, " \| "))}")	1✔
161	for (i, row) in enumerate(md.rows)	2✔
162	for (j, cell) in enumerate(row)	2✔
163	j != 1 && print(io, " & ")	4✔
164	latexinline(io, cell)	4✔
165	end	6✔
166	println(io, " \\\\")	2✔
167	if i == 1	2✔
168	println(io, "\\hline")	1✔
169	end
170	end	2✔
171	end
172	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