Questions tagged [performance]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
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. ...
user avatar
  • 111
0 votes
0 answers
14 views

How to draw a Markov chain model for this simulation

A node of a data communication network which can transmit data at 4 different rates r, 2r, 3r & 4r uses the mechanism described below to control congestion: At any given time the node is ...
user avatar
1 vote
0 answers
17 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, ...
user avatar
1 vote
1 answer
106 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 ...
user avatar
  • 31
0 votes
1 answer
28 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 ...
user avatar
0 votes
0 answers
34 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 ...
user avatar
  • 191
1 vote
0 answers
32 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? ...
user avatar
  • 386
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 ...
user avatar
1 vote
0 answers
21 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 ...
user avatar
0 votes
0 answers
37 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 ...
user avatar
  • 105
2 votes
0 answers
55 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 ...
user avatar
1 vote
1 answer
330 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 ...
user avatar
0 votes
1 answer
59 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 ...
user avatar
1 vote
1 answer
116 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 ...
user avatar
0 votes
0 answers
12 views

Analysis of straggler in tree-based parallel execution

Does anyone have a reference on how tree-based parallel execution can reduce the chance of getting a straggler. Google Dremel and Jeff Dean's talk at slide 53 both talk about using tree-based parallel ...
user avatar
0 votes
0 answers
51 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 ...
user avatar
  • 101
0 votes
0 answers
37 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 ...
user avatar
  • 131
1 vote
2 answers
155 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 ...
user avatar
3 votes
0 answers
73 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: ...
user avatar
1 vote
0 answers
44 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 ...
user avatar
  • 111
0 votes
1 answer
88 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 ...
user avatar
  • 103
0 votes
1 answer
66 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 ...
user avatar
  • 229
0 votes
1 answer
702 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 ...
user avatar
0 votes
1 answer
24 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,...
user avatar
0 votes
1 answer
550 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 ...
user avatar
  • 113
1 vote
1 answer
82 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 ...
user avatar
2 votes
2 answers
178 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{...
user avatar
  • 135
0 votes
1 answer
32 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 ...
user avatar
-1 votes
1 answer
176 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 ...
user avatar
  • 1
0 votes
1 answer
61 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 ...
user avatar
0 votes
1 answer
140 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 ...
user avatar
4 votes
1 answer
191 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 ...
user avatar
0 votes
2 answers
2k 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 ...
user avatar
  • 73
4 votes
2 answers
2k 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 ...
user avatar
  • 85
1 vote
2 answers
37 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 ...
user avatar
  • 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 ...
user avatar
0 votes
1 answer
93 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 ...
user avatar
  • 145
0 votes
1 answer
55 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 ...
user avatar
  • 215
1 vote
1 answer
38 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 ...
user avatar
  • 135
2 votes
2 answers
77 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 ...
user avatar
  • 201
1 vote
1 answer
386 views

How to prove the performance, Big Omega ,of building a binary heap using recursive method is Ω(nlog(n))

We can learn the big-O of building a binary heap using recursive method is O(n log n) from wiki "This approach, called Williams’ method after the inventor of binary heaps, is easily seen to run in O(n ...
user avatar
  • 13
1 vote
1 answer
55 views

Slowdown when accessing data at page boundaries?

Hi I have a program which accesses memory words that are located X bytes apart in virtual address space. For instance, ...
user avatar
  • 113
0 votes
2 answers
31 views

How to properly compare performance of a prototype against a baseline

Assume that we have a baseline software B and a new prototype P that I want to compare with B. Ideally, I want to show that P performs some orders of magnitude or X times faster than B (on average). ...
user avatar
  • 101
-1 votes
2 answers
2k views

Confusion in speed up calculation for pipeline architecture

This is an online question I am trying to solve. You are given a non-pipelined processor design which has a cycle time of 10ns and average CPI of 1.4.If a pipelined processor having 5 stages are 1ns, ...
user avatar
  • 229
1 vote
0 answers
36 views

Can graph execution be better optimized than imperative programs?

I've been reading about Google's TensorFlow, and the way it represents calculations with graphs that are then executed by an engine. While the concept is interesting, I would like to understand why ...
user avatar
  • 111
0 votes
2 answers
727 views

Importance of Frequency vs CAS Latency in memory performance

I was looking at the Wikipedia page for CAS Latency: https://en.wikipedia.org/wiki/CAS_latency And I noticed the obvious trend - at higher frequency, despite CAS latency degrading (growing), the ...
user avatar
1 vote
1 answer
134 views

Looking for algorithm to iterate over matrix

I have such a product example: ...
user avatar
3 votes
1 answer
173 views

Performance of Modified Dijkstra's algorithm with Binariy heap as Priority Queue

we know the performance of Dijkstra's algorithm with binary heap is O(log |V |) for delete_min, O(log |V |) for insert/ decrease_key, so the overall run time is O((|V|+|E|)log|V|). Now let's modify ...
user avatar
  • 113
3 votes
1 answer
372 views

d-ary heap implementation vs Fibonacci heap implementation Dijkstra performance comparions

Let's say that Dijkstra’s algorithm with the priority queue using a d-ary heap. if adjusting d, we can try to achieve the best runtimes for the algorithm with d being $\sim |E|/|V|$. Then for a ...
user avatar
1 vote
0 answers
47 views

Accuracy and performance between a division and subtraction for a ratio in decibels

For comparing two images, one can use the Peak Signal-to-Noise Ratio (PSNR) metric, defined as follows: $\mathrm{PSNR} = 10 \cdot \log_{10}\left(\frac{\mathrm{MAX}^2}{\mathrm{MSE}}\right) = 20 \cdot \...
user avatar
  • 111