Skip to main content

Questions tagged [performance]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
2 votes
1 answer
113 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 ...
ccot's user avatar
  • 123
4 votes
2 answers
86 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 ...
CPlus's user avatar
  • 207
2 votes
4 answers
70 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 ...
simd's user avatar
  • 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, ...
securityauditor's user avatar
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 ...
Adeesh Lemonickous's user avatar
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 ...
Logan R. Kearsley's user avatar
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) ---...
Grigori's user avatar
  • 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 ...
alpominth's user avatar
  • 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 ...
Enyium's user avatar
  • 11
4 votes
2 answers
118 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 (...
CodeNoob's user avatar
  • 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 : ...
brubsby's user avatar
  • 153
0 votes
2 answers
176 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 ...
BatWannaBe's user avatar
0 votes
1 answer
227 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 ...
Papillon's user avatar
  • 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 ...
rayhem's user avatar
  • 173
0 votes
3 answers
200 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 ''...
fulem's user avatar
  • 23
1 vote
2 answers
155 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 ...
NoName123's user avatar
  • 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/...
AHF's user avatar
  • 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. ...
mmackh's user avatar
  • 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, ...
HelterSkelter's user avatar
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 ...
xyf's user avatar
  • 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 ...
empleat's user avatar
  • 103
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 ...
Foad's user avatar
  • 201
1 vote
0 answers
144 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? ...
user76284's user avatar
  • 416
0 votes
0 answers
20 views

Is arithmetic/constants code optimization a function of the Language/Compiler/CPU/ALU/OS and what languages implement such features in itself?

Take the following case ...
newInt1x1's user avatar
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 ...
Vectorizer's user avatar
0 votes
0 answers
175 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 ...
StarBuck's user avatar
  • 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 ...
Ilya Loskutov's user avatar
4 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 ...
user1887919's user avatar
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 ...
Abhishek Ghosh's user avatar
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 ...
Question's user avatar
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 ...
Karup's user avatar
  • 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 ...
Eminem's user avatar
  • 131
1 vote
2 answers
268 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 ...
CafféSospeso's user avatar
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: ...
Kirill Lykov's user avatar
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 ...
jolene's user avatar
  • 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 ...
Melanie's user avatar
  • 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 ...
Lightsong's user avatar
  • 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 ...
Haslo Vardos's user avatar
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,...
Sayaman's user avatar
  • 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 ...
HotWheels's user avatar
  • 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 ...
Questioner's user avatar
2 votes
2 answers
955 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{...
timtam's user avatar
  • 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 ...
VimForLife's user avatar
-1 votes
1 answer
535 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 ...
hwinl's user avatar
  • 1
1 vote
1 answer
180 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 ...
BovineScatologist's user avatar
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 ...
BovineScatologist's user avatar
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 ...
Silver Flash's user avatar
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 ...
Www's user avatar
  • 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 ...
Marcelo Glasberg's user avatar
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 ...
D. B.'s user avatar
  • 21