Questions tagged [performance]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0
votes
0answers
13 views

How to model internal queues shared between services in queueing networks

I am trying to model a load balancer as a queueing network. The load balancer has a number $n$ of internal threads. There is a central queue of requests from which the threads are fed. Each thread ...
1
vote
1answer
31 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 ...
1
vote
1answer
40 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, ...
0
votes
2answers
22 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). ...
0
votes
2answers
77 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, ...
1
vote
0answers
15 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 ...
0
votes
1answer
50 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 ...
1
vote
1answer
64 views

Looking for algorithm to iterate over matrix

I have such a product example: ...
3
votes
1answer
102 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 ...
3
votes
1answer
166 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 ...
1
vote
0answers
44 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 \...
6
votes
1answer
76 views

Do most computational efficiency increases due to increased transistor count in the last 70 years depend on some kind of parallelism?

Modern personal computers as far as I understand have increased in power (measured informally by ability to compute “more demanding programs”) due to two “broad factors”: decreased transistor size (...
2
votes
1answer
5k views

Cache effective access time calculation

In order to calculate the effective access time of a memory sub-system, I see some different approaches, a.k.a formulas. All are reasonable, but I don't know how they differ and what is the correct ...
3
votes
1answer
223 views

Maximum number of segments with no intersection [duplicate]

This is an interview question. Suppose you have an array of n segments, when each segment is a pair of two integers: start point and end point. For example: ...
1
vote
1answer
90 views

How to describe the time complexity of a continually running program with a stream of inputs?

Maybe time complexity isn't the right term. Performance? There must be some way of describing the efficiency of a program over time. For instance, I recently had a part of a program that took a ...
-1
votes
1answer
25 views

Performance - Computer Organization and design

A popular app takes 10 seconds to execute on a 11 watt smartphone A, and it takes 8 seconds to execute on a 13 watt smartphone B. The app is a bigger drain on the battery on which smartphone?
0
votes
1answer
30 views

How to show that i have significant improvements over the baselines?

I had review feedbacks regarding my recent publications and reviewers argued that the improvements are not significant over the baselines. I tried my classification algorithm on some image datasets ...
-1
votes
2answers
94 views

Big-O notation analysis [duplicate]

Can I get help to give an analysis of the running time Big-O? I'm not sure if all my answers are correct. I got for a) $ O(n)$, b) $O(n^3)$, c) $O(n^{1/2})$ and d) $O(log(n))$ ...
0
votes
1answer
69 views

Finding maximum clique in a distance matrix created by certain pattern

I have a distance matrix which is created through a predefined pattern (or formula) and I want to find elements with minimum distance "d" from each other, in order to do that I search for the maximum ...
1
vote
0answers
44 views

Operation count: Solving Ax=b with sparse diagonal matrix

I've seen several tables that list operation counts for matrix-inversion related problems, but none of them actually brought forward the way of computing them. I'm interested in solving ...
0
votes
0answers
28 views

How to define a generic evaluation metric

Given a system (S) that accepts a tuple of parameters ($\alpha, \beta, \gamma \dots$ etc). These parameters affect the performance of S in a different way. For instance, decreasing $\alpha$ would ...
2
votes
1answer
568 views

Recursive functions from O(n) complexity to O(log n)

For some recursive questions that require recursing on an input with a small piece removed (hence linear in the size of the input), can we reduce run time by recursing on two halves of the input each ...
4
votes
1answer
2k views

Is Timsort more efficient than merge sort and why?

I was just wondering, I think merge sort is more efficient but not sure if that is true. I know it's to do with the complexities but am still struggling to understand.
1
vote
1answer
205 views

Trilinear interpolation for distorted cubes?

Is there a variation of trilinear interpolation that works on a "cube" that has been distorted (by moving one or more of its corners by an arbitrary amount into an arbitrary direction)? I know that I ...
0
votes
1answer
31 views

What do you call a lower/upper bound that is the best one?

I have developed an upper bound on the number of vertices of a particular graph. This bound is the best possible bound that can be found for any given instance. What do you call such a bound? If it ...
0
votes
0answers
130 views

Amdahl's Law when the speedup of new component = ∞

I was doing a problem about Amdahl's Law when I noticed that $s,(local$ $ speed-up)$ was incalculable. The wording: A computer takes 100 seconds to execute a program. The multiplication operations ...
3
votes
1answer
569 views

Variable size and CPU performance

When you learn programming they tell you choose data types that suffice for the concepts you're expressing, i.e. not too small because then your data won't fit and not too big because you don't want ...
1
vote
1answer
770 views

How to handle the repeat until convergence condition in time complexity and summarize the time complexity? [closed]

I am a novice in complexity calculation. I need to calculate the overall time complexity. My attempt is given below: Here, N = number of data points (N>300), C ...
0
votes
0answers
122 views

Probability in Dynamic frame aloha

If I've RFID Collision Arbitration System that is based on multi-frame dynamic frame ALOHA. How can compute the probability of the average tag resolution $L_n$? ,$P_s$ is probability for packet ...
-1
votes
1answer
4k views

How do I calculate the speedup properly?

I am trying to calculate the speedup of this, but I am getting the wrong answer: Assuming that we have a program where we have two execution phases. One phase takes 1 time unit to execute and can ...
0
votes
1answer
41 views

Difference in scale between mean page loading times and exponentially distributed page loading times?

Apologies if this is the wrong place to ask. For my experiment, I have a single-page application and a multi-page application. I am testing them with an exponential distributed delay throttling. The ...
2
votes
2answers
165 views

Sorting networks hybrid sort

I saw an answer about the fastest way to sort an array with 6 elements. Turns out that using a sorting network is the best choice. If sorting networks are the fastest way to sort a small(< 16 ...
1
vote
2answers
61 views

Are fractions more computationally “expensive” than whole numbers?

I have a problem where the values are represented to humans as [0, .5, 1, ..., 8] But the function is massively recursive (game trees for a set of increasingly intractable problems) so I'm wondering ...
2
votes
1answer
74 views

What is the basic idea behind the usage of TLBs?

I know how Translation Lookaside Buffers work, and i also know we use them to improve the performance of data/program access by storing the recent page numbers - frame numbers in a memory cache. The ...
8
votes
2answers
268 views

GCD of a pair of products

I have two numbers, which are each the product of a large number of smaller numbers that I know. I want to find the GCD (Greatest common divisor) of these two numbers. Is there any way I can make use ...
2
votes
1answer
250 views

Changing Rabin-Karp without modulo to Rabin-Karp with modulo

I am trying to solve a string matching problem using Rabin-karp algorithm. I made use of Horner's method for calculating hash function, but I forgot to use modulo operator. It's like this now. (this ...
1
vote
1answer
37 views

Estimating the run time of a program according to a given CPU performance

When we have a recurrence relation of a program, as an example: T(N) = N log N + 9N + 55 and the CPU capability let's say (10^6) or any other number. What is ...
0
votes
0answers
517 views

What is the Effect of Hidden Layer Size?

I aim to gain more intuition with regards to the role of a hidden layer in a neural network architecture. And further to understand whether my classification problem is a linear one or not. Here is ...
1
vote
0answers
222 views

Tips for improving implementation of Wagner-Fischer-algorithm

So I'm working on an implementation of a Wagner-Fischer-Algorithm for an online programming challenge site, but I can't seem to push the time down to where it needs to be. The assignment is to, for a ...
2
votes
3answers
126 views

Why computer take long time to open huge text files? [closed]

Im not sure if this the right place to ask but I'm wondering why a computer takes forever to open huge text file like 1GB but if I open a video file (mkv) for example with 10GB like a movie it will be ...
3
votes
1answer
370 views

Best way to merge different trees to single data structure?

I trained an XGBoost model that classifies 50 different classes, therefore it generates a lot of boosters (trees). Also, I wrote a script that turns trained model to C++ code and it works really fast ...
2
votes
1answer
678 views

Understanding Amdahl's Law calculation

I have a homework problem: Calculate the overall speedup of a system that spends 40% of its time in calculations with a processor upgrade that provides for 100% greater throughput. Which is a pretty ...
0
votes
1answer
48 views

The impact of caching on the system performance or on the user experience

I am working on modeling a certain system's cache layer and comparing two algorithms. One outperforms the other one; it shows the higher cache hit rate (%). But what is important is the impact of ...
1
vote
1answer
44 views

How to measure the degree of randomness in Disk I/Os?

Most disk-based system's performance heavily depends on its disk access patterns. So maximizing the sequential I/Os while avoiding the random I/Os is a typical goal in performance perspective. I am ...
11
votes
4answers
1k views

Why do we have to trade abstraction for speed?

Why can high-level languages seemingly never reach lower-level languages in terms of speed? Examples of high-level languages would be Python, Haskell, and Java. Low-level languages would be trickier ...
0
votes
0answers
249 views

Hashtable vs cache-oblivious

This question has been asked in the theoretical community, but deemed as too practical. I am moving it here, I hope it is on-topic. I'd like to know more about real performances of data structures, ...
0
votes
0answers
72 views

Performance on modifying cycle time

I learnt in my computer architecture course on Caches, that if we keep the memory speed of a machine the same and half the clock cycle time, the miss penalty doubles. Why does this happen? What is ...
3
votes
1answer
89 views

Is the memory usage of total languages deterministic?

I'm interested in the memory usage of various programming languages when implemented on actual hardware. I believe that a Turing-complete programming language has, in general, unknowable memory usage ...
10
votes
3answers
2k views

Why is a (collision-less) hashtable lookup really O(1)?

Disclaimer: I know there are similar sounding questions already here and on Stackoverflow. But they are all about collisions, which is not what I am asking for. My question is: why is collision-less ...