Questions tagged [performance]
The performance tag has no usage guidance.
150
questions
2
votes
1
answer
106
views
Tree algorithm - arrange integer array numbers to form largest number
I have solved leetcode's Largest Number.
I am asking another question about it here, more from a theory perspective about "if" I had used a tree for the solution. I have a full functioning ...
- 123
4
votes
2
answers
85
views
Why do benchmark results vary at all?
Benchmarking typically consists of getting the current CPU time, executing test code a large number of times, and then subtracting the new CPU time from the previous one. However when you benchmark ...
- 207
2
votes
4
answers
69
views
Are float pseudo-random number generators always implemented using integer generators underneath
In C it's well known to use simple routine for turning integer rng into float rng. Something like that
...
- 121
0
votes
2
answers
88
views
Why does Elbrus use VLIW architecture?
I find the Russian Elbrus CPU fascinating.
It seems that it is fairly decent at performing calculations, and security. This is likely as it is heavily specific for military and financial industries, ...
- 101
0
votes
1
answer
47
views
Counting the expected number of CPU cycles for n-number of assembly instructions
I was trying to count the cpu_cycles from an ARM processor 4 core Cortex A78 to be exact) using the PMU registers. Now, at the beginning, I read the cpu cycles counter register, then for test just run ...
0
votes
0
answers
27
views
Applying permutations with moves rather than swaps
Everything I can easily find on applying permutations in-place relies on treating swaps as elementary operations. But in reality, every swap requires at least two moves (to move the first item into ...
1
vote
1
answer
65
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) ---...
- 105
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
172
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
117
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
61
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
2
answers
174
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
226
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
6
votes
3
answers
1k
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 ...
- 173
0
votes
3
answers
198
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
151
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 ...
- 171
0
votes
1
answer
129
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
2k
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
139
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
40
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
143
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
48
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
174
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 ...
- 137
2
votes
0
answers
170
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
3
votes
1
answer
2k
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 ...
- 131
0
votes
1
answer
179
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,132
1
vote
1
answer
322
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
81
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
61
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
266
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
141
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
51
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
249
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 ...
- 113
0
votes
1
answer
89
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
27
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
1k
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
143
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
945
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
51
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
532
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
179
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
...
1
vote
1
answer
265
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
383
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
5k
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