Questions tagged [performance]
The performance tag has no usage guidance.
145
questions
0
votes
0
answers
22
views
Impact of label flipping on ROC-AUC score
I was exploring a problem of label flipping in the target column:
Problem:
I have a data frame with just two columns: Predicted probability | Target. Target column is binary (contains only 0 and 1) ---...
- 65
1
vote
0
answers
21
views
Does copying/moving data between variables consumes less cycles per byte than adding/rotating/xoring?
A round of Salsa20 is done as follows:
b ^= (a + d) <<< 7;
c ^= (b + a) <<< 9;
d ^= (c + b) <<< 13;
a ^= (d + c) <<< 18;
The ...
- 111
1
vote
1
answer
168
views
Iterating over combinations of 4 timestamps from 2 timelines *efficiently*
I need help in finding a more performant algorithm.
I have two timelines in the form of two indexed lists where each element is a floating-point value that represents seconds. The values in each list ...
- 11
4
votes
2
answers
115
views
Data structure to estimate the frequency of low frequency elements
I have a file with trillions of numbers and I want to get all numbers that have a frequency <=100. These numbers are in text format (...
- 141
2
votes
1
answer
55
views
Are there any mathematical properties of consecutive integer power modulo operations that could be exploited for algorithmic speed gain?
I'm attempting to search through all the integers between 10^15 and 10^16 to check if they are in the oeis sequence A277274, and the entirety of the program can be summarized as mostly equivalent to :
...
- 153
0
votes
0
answers
29
views
What should be the expected performance of programs coded in Scheme with manual memory management?
I have been seeing benchmarks of some Scheme implementations and taking Chicken as an example, it is about 4 to 6 times slower than C.
An (obvious) option is to code in Scheme would be getting rid of ...
- 101
0
votes
2
answers
120
views
Is a specialized hardware instruction always faster than a software implementation, and if so, is there a general reason?
I started wondering this after reading about the x86-SSE instruction rsqrtss being faster (and more accurate) than the Fast inverse square root. I have also read ...
- 357
0
votes
1
answer
179
views
Why do computers become slow over time (HW PoV)?
I'm a SW engineer. I'm just curious why computers become slow over time.
"Slow" here I mean from a usual user PoV:
It takes more time to launch an application.
Application UI takes longer ...
- 103
4
votes
3
answers
632
views
Are there absolute reasons to prefer row/column-major memory ordering?
I've heard it said that "fortran uses column-major ordering because it's faster" but I'm not sure that's true. Certainly, matching column-major data to a column-major implementation will ...
- 153
0
votes
3
answers
141
views
Super-linear parallelism or speedup in parallel matrix multiplication algorithms
I'm reading this slides from a MIT course on parallel software performance. They introduced the concepts of Work $T_1$, Span $T_\infty$ and Parallelism (ratio $T_1/T_\infty$). What is called ''...
- 23
1
vote
2
answers
70
views
Forwarding in pipelined processors can increase throughput by decreasing amount of stalls, but can it in some cases impair performance?
Pipelined processors suffer from stalls due to different kind of hazards and one way of dealing with it is to implement forwarding of different types. For example ALU-ALU forwarding or full forwarding ...
- 141
0
votes
1
answer
127
views
What can be the topic of my assignment for presentation about overall computing performance?
I have received the below question for presentation. It was random assignment, its not my field. What is this specifically in Computer Architecture?
how CPU and GPU architecture, memory bandwidth/...
- 97
1
vote
0
answers
30
views
Grouping only overlapping points into stacks
I have n number of files on a ScrollView. Every time a file is added, x/y coordinates are stored in an array. The user is able to drag and drop the files anywhere they like. Overlapping files (e.g. ...
- 111
1
vote
0
answers
25
views
Why does an N retries failure rate is $(1-x)^N$?
I read this blog post Fixing retries with token buckets and circuit breakers (by Marc Brooker), which goes through several retry strategies.
For the "N retries" strategy (i.e. on failure, ...
1
vote
1
answer
939
views
Reasoning behind specifically doubling the array size upon reallocation
I am trying to understand the actual reasoning behind creating a new dynamic array of double the size of the original array once it gets full as opposed to any reasonably random number (not too small ...
- 127
0
votes
2
answers
134
views
Determining runtime of a theoretical program (question of extraordinary complexity)?
I apologize in advance, as I don't have a clue to which stackexchange to post this question! I beg you to not delete this question, as I have chronic pain and it is very important to me!!! I actually ...
- 3
0
votes
0
answers
37
views
What is the most performant and reliable algorithm to find all roots of a nonlinear function within a range?
Following this question on MATLAB's Discord channel, I did a bit of search and found this interesting answer using circshift() function to detect zero-crossings. I ...
- 201
1
vote
0
answers
90
views
CEK machine vs SECD machine
What are the differences between the CEK machine and the modern variant of the SECD machine (which combines stack and dump) from the point of view of performance, memory efficiency, and other factors? ...
- 416
0
votes
0
answers
20
views
1
vote
0
answers
44
views
(Branchless) Bitonic Sorting Network for a Set of Floating Point Numbers
In the past I've implemented a branchless Bitonic Sorting Network on a gpu using CUDA, for integers.
I am facing a related problem:
In my Order Independent Transparency implementation, I would like to ...
- 135
0
votes
0
answers
93
views
Is there a way to convert FLOPS to bit operation per second
My problem is the following: I have $N$ inner products to compute in parallel every second.
Each of the vectors in those inner product is composed of $7$ bits.
I want to know for which $N$ it starts ...
2
votes
0
answers
131
views
CPU utilization estimation
In the Modern Operating System by Andrew Tanenbaum, Herbert Bos the authors provide their explanation of the concept of CPU utilization in the following way:
A better model is to look at CPU usage ...
- 217
1
vote
1
answer
1k
views
What is the difference between FLOPS and OPS?
I have typically heard computer performance discussed in terms of FLOPS.
However, I have recently seen multiple references instead using OPS i.e. operations per second, typically in the context of Big ...
- 111
0
votes
1
answer
143
views
Confusion regarding calculation of estimated memory access time in a system containing only a cache and main memory for simplicity
Let us consider a system having cache and main memory. Now suppose we are asked to find the average memory access time. Let $h$ be the hit ratio for the cache, $t_c$ be the cache access time, $t_m$ be ...
- 1,092
1
vote
1
answer
235
views
Do more registers increase clock cycle time?
While reading a book on computer organization, I ran into a design principle stating that "smaller is faster", indicating that fewer registers means less clock cycle time. Could you prove ...
- 11
0
votes
0
answers
78
views
Distributed Algorithm to get an ordered list of nodes in a bipartite graph
Given a weighted bipartite graph with nodes of type A and B, I want to output an (approximately) ordered list of type B nodes as defined by the following heuristic:
For each node of type B, sum over ...
- 101
0
votes
0
answers
58
views
Minimum number of elements in AVL tree to make it worth creating
Given an AVL tree containing nodes ordered by unique integer I.D's and data as pointers to some struct, what would be the expected minimum number of elements that will justify the creation and ...
- 131
1
vote
2
answers
234
views
Fast computing of a matrix power for large integer values in C++
I'm working with squared matrices that can be quite large, for instance, a M = 50 x 50 matrix.
My objective is to compute the power of the squared matrix ...
- 113
3
votes
0
answers
106
views
How to detect when to use radix sort in runtime
I'm implementing a stable integer sorting algorithm, I've chosen radix sort. I've tested LSD vs MSD implementation, wrote MSD/LSD hybrid implementation to reduce bandwidth pressure. The repo is here: ...
- 131
1
vote
0
answers
46
views
The correct way to calculate the performance of my approximate algorithm
I've got a question about how best to classify the performance of an approximate algorithm. I'm trying to find the 'correct' value of a graph problem instance whose cost function has an objective ...
- 111
0
votes
1
answer
202
views
Analyzing parallel performance question
I was reviewing for my CS class and came across this question and answer combo that didn't have any explanation why it was correct. I'm confused on how they got the answer:
We have a system to which ...
- 103
0
votes
1
answer
83
views
Interesting Speedup & Amdahl's law problem
I have found a problem on my Computer Architecture textbook which I have some issues with:
We have a process which spends its time in the following way:
50% of the time, it executes common ...
- 239
0
votes
1
answer
2k
views
Metrics on which Clock Cycles Per Instruction(CPI) depends
In the book - Computer Organization and Design: The Hardware/Software Interface [RISC-V Edition] by Patterson and Hennessy, CPI is defined like this:
The term clock cycles per instruction, which is ...
- 147
0
votes
1
answer
26
views
Is it possible to generate a better random number generator algorithm from an algorithm that use N computers with one that uses N+1 computers?
Is it possible to generate a better random number generator algorithm from an algorithm that use N number of computers with an algorithm that uses N+1 number of computers? I use the word computer here,...
- 117
0
votes
1
answer
984
views
Calculating CPU throughput on a single cycle vs multicycle datapath
When calculating the throughput of a CPU, how does it differ when it is implemented with a single cycle datapath versus a multicycle datapath? If for example the CPU is running 1 GHz freq, then ...
- 113
1
vote
1
answer
124
views
Most scalable distributed consensus mechanism based on message complexity?
One of the most challenges in distributed consensus mechanisms is both time complexity and message complexity.
For example, PBFT message complexity is O(n^2) that ...
- 145
2
votes
2
answers
593
views
Why is $\log n+\log \frac{n}{2}+\log \frac{n}{4}+\log \frac{n}{8}+\cdots+\log \frac{n}{n}=\Theta (\log^2 n)$?
$$\log n+\log \frac{n}{2}+\log\frac{n}{4}+\log\frac{n}{8}+\cdots+\log\frac{n}{n}=\Theta (\log^2n).$$
The sum of logarithms is the logarithm of the product $n\cdot\frac{n}{2}\cdot\frac{n}{4}\cdot\frac{...
- 135
0
votes
1
answer
47
views
MAC protocol with throughput of 1
Consider a MAC protocol (ALOHA, CSMA, TDMA, etc.) that, even for very high loads, always results in a throughput of 1 (normalized with respect to the channel speed).
Why is that not good if the ...
- 125
-1
votes
1
answer
408
views
How to compute the max. speedup achievable of parallel program?
I was given the following problem to solve:
Consider a system that has 128 compute units of the same type. Suppose that a program runs for 1025 time units on a single compute unit. The total amount ...
- 1
1
vote
1
answer
137
views
MIPS pipeline: choosing between slowing down a stage and adding a new stage
Suppose a new, more complicated, instruction is desired for this
simple pipelined MIPS processor. Suppose, also, it could be
implemented by either (a) adding new logic to the execute stage of the
...
0
votes
1
answer
242
views
Help with performance and speed-up question related to number of cores and their areas
There is a question in my exam that said:
Consider the following three processors (x, y, and z) that are all of varying areas. Assume that the single-thread performance of a core increases with the ...
4
votes
1
answer
309
views
Doubt on Performance Comparison of Splay Trees
I'm trying to understand splay tree performance compared to a standard balanced tree like AVL/red-black. In practice, I am pretty skeptical of the amortized bounds Tarjan and Sleator proves in their ...
- 205
0
votes
2
answers
4k
views
Average access time in two level cache system
In a two-level cache system, the level one cache has a hit time of 1 ns (inside the CPU), hit rate of 90%, and a miss penalty of 20 ns. The level two cache has a hit rate of 95% and a miss penalty of ...
- 73
4
votes
2
answers
3k
views
What's an efficient algorithm to calculate line breaks (word wrap) for balanced widths (minimum raggedness)?
This is a real-world application, not a student assignment.
Suppose we have some numbered boxes which are to be laid out, in order, from left to right, top to bottom, with no space between them, into ...
1
vote
2
answers
38
views
Time efficient way to implement Multi-Armed-Bandits?
I'm doing a research on Multi-Armed Bandit (MAB) problem with approx. 1 million arms. In contrast, the number of iterations is of course much larger, about 10-20 million.
Most MAB-algorithms require ...
- 21
0
votes
1
answer
28
views
F-measure with $\beta > 1$
Consider the F-measure $F_{\beta}$. I know that with $\beta < 1$ precision is given more importance, ending with $F_{0} = precision$. With $\beta > 1$ means recall gets the upper hand, with the ...
- 251
0
votes
1
answer
139
views
Performance speedup with Amdahl's law
Consider this question: A program has 1M instructions and 30% of them are SQRT with CPI=8. The CPI of the rest of the instructions are 3. If we reduce the CPI of SQRT to 2, how much speedup is ...
- 145
0
votes
1
answer
70
views
Classification accuracy based on top 3 most likely classifications
My goal is to recommend jobs to job seekers based on their skill set.
Currently I'm using an SVM for this, which is outputting one prediction, e.g. "software engineer at Microsoft". However, consider ...
- 215
1
vote
1
answer
45
views
Simplification of a multi-index Boolean expression towards computation in fewer steps
Let $x_{ij} \in \{0,1\}$, $1 \leq i \leq M$ (typically, $M = 2000$), $1 \leq j \leq N$ (typically, $N = 10$), be Boolean variables. If possible at all, I would like to simplify the following ...
- 135
2
votes
2
answers
130
views
Minimum words in a string given a dictionary
The question is: Given a dictionary consisting of a set of words and a string: find the minimum number of words the string can be split into. If the string can not be decomposed into a list of words ...
- 211