




class        __lowerCAmelCase					:







			def __init__(			self       :     Dict       ,       snake_case__       :     Optional[int] ):




									"""simple docstring"""


									_UpperCAmelCase						=	val
									# Number of nodes in left subtree
									_UpperCAmelCase						=	0
									_UpperCAmelCase						=	None
									_UpperCAmelCase						=	None
									_UpperCAmelCase						=	None







			def UpperCamelCase     (			self       :     str       ,       snake_case__       :     Any ):




									"""simple docstring"""


									assert self.left_tree_size == other.left_tree_size, "Unequal Sizes of Blocks"

									if self.val < other.val:
															_UpperCAmelCase						=	self.right
															_UpperCAmelCase						=	None
															if self.right:
																					_UpperCAmelCase						=	other
															_UpperCAmelCase						=	other
															_UpperCAmelCase						=	self.left_tree_size * 2 + 1
															return self
									else:
															_UpperCAmelCase						=	other.right
															_UpperCAmelCase						=	None
															if other.right:
																					_UpperCAmelCase						=	self
															_UpperCAmelCase						=	self
															_UpperCAmelCase						=	other.left_tree_size * 2 + 1
															return other






class        __lowerCAmelCase					:







			def __init__(			self       :     List[str]       ,       snake_case__       :     str=None       ,       snake_case__       :     Union[str, Any]=None       ,       snake_case__       :     Tuple=0 ):




									"""simple docstring"""


									_UpperCAmelCase						=	heap_size
									_UpperCAmelCase						=	bottom_root
									_UpperCAmelCase						=	min_node







			def UpperCamelCase     (			self       :     Optional[int]       ,       snake_case__       :     List[Any] ):




									"""simple docstring"""


									if other.size == 0:
															return None
									if self.size == 0:
															_UpperCAmelCase						=	other.size
															_UpperCAmelCase						=	other.bottom_root
															_UpperCAmelCase						=	other.min_node
															return None
									# Update size
									_UpperCAmelCase						=	self.size + other.size

									# Update min.node
									if self.min_node.val > other.min_node.val:
															_UpperCAmelCase						=	other.min_node
									# Merge

									# Order roots by left_subtree_size
									_UpperCAmelCase						=	[]
									_UpperCAmelCase				,					_UpperCAmelCase						=	self.bottom_root, other.bottom_root
									while i or j:
															if i and ((not j) or i.left_tree_size < j.left_tree_size):
																					combined_roots_list.append((i, True) )
																					_UpperCAmelCase						=	i.parent
															else:
																					combined_roots_list.append((j, False) )
																					_UpperCAmelCase						=	j.parent
        # Insert links between them
									for i in range(len(snake_case__ ) - 1 ):
															if combined_roots_list[i][1] != combined_roots_list[i + 1][1]:
																					_UpperCAmelCase						=	combined_roots_list[i + 1][0]
																					_UpperCAmelCase						=	combined_roots_list[i][0]
        # Consecutively merge roots with same left_tree_size
									_UpperCAmelCase						=	combined_roots_list[0][0]
									while i.parent:
															if (
															    (i.left_tree_size == i.parent.left_tree_size) and (not i.parent.parent)
															) or (
															    i.left_tree_size == i.parent.left_tree_size
															    and i.left_tree_size != i.parent.parent.left_tree_size
															):
																					# Neighbouring Nodes
																					_UpperCAmelCase						=	i.left
																					_UpperCAmelCase						=	i.parent.parent

																					# Merging trees
																					_UpperCAmelCase						=	i.merge_trees(i.parent )

																					# Updating links
																					_UpperCAmelCase						=	previous_node
																					_UpperCAmelCase						=	next_node
																					if previous_node:
																											_UpperCAmelCase						=	i
																					if next_node:
																											_UpperCAmelCase						=	i
															else:
																					_UpperCAmelCase						=	i.parent
        # Updating self.bottom_root
									while i.left:
															_UpperCAmelCase						=	i.left
									_UpperCAmelCase						=	i

									# Update other
									_UpperCAmelCase						=	self.size
									_UpperCAmelCase						=	self.bottom_root
									_UpperCAmelCase						=	self.min_node

									# Return the merged heap
									return self







			def UpperCamelCase     (			self       :     Any       ,       snake_case__       :     Optional[int] ):




									"""simple docstring"""


									if self.size == 0:
															_UpperCAmelCase						=	Node(snake_case__ )
															_UpperCAmelCase						=	1
															_UpperCAmelCase						=	self.bottom_root
									else:
															# Create new node
															_UpperCAmelCase						=	Node(snake_case__ )

															# Update size
															self.size += 1

															# update min_node
															if val < self.min_node.val:
																					_UpperCAmelCase						=	new_node
															# Put new_node as a bottom_root in heap
															_UpperCAmelCase						=	new_node
															_UpperCAmelCase						=	self.bottom_root
															_UpperCAmelCase						=	new_node

															# Consecutively merge roots with same left_tree_size
															while (
															    self.bottom_root.parent
															    and self.bottom_root.left_tree_size
															    == self.bottom_root.parent.left_tree_size
															):
																					# Next node
																					_UpperCAmelCase						=	self.bottom_root.parent.parent

																					# Merge
																					_UpperCAmelCase						=	self.bottom_root.merge_trees(self.bottom_root.parent )

																					# Update Links
																					_UpperCAmelCase						=	next_node
																					_UpperCAmelCase						=	None
																					if next_node:
																											_UpperCAmelCase						=	self.bottom_root







			def UpperCamelCase     (			self       :     List[Any] ):




									"""simple docstring"""


									return self.min_node.val







			def UpperCamelCase     (			self       :     Any ):




									"""simple docstring"""


									return self.size == 0







			def UpperCamelCase     (			self       :     Optional[int] ):




									"""simple docstring"""


									_UpperCAmelCase						=	self.min_node.val

									# Last element in heap corner case
									if self.size == 1:
															# Update size
															_UpperCAmelCase						=	0

															# Update bottom root
															_UpperCAmelCase						=	None

															# Update min_node
															_UpperCAmelCase						=	None

															return min_value
									# No right subtree corner case
									# The structure of the tree implies that this should be the bottom root
									# and there is at least one other root
									if self.min_node.right is None:
															# Update size
															self.size -= 1

															# Update bottom root
															_UpperCAmelCase						=	self.bottom_root.parent
															_UpperCAmelCase						=	None

															# Update min_node
															_UpperCAmelCase						=	self.bottom_root
															_UpperCAmelCase						=	self.bottom_root.parent
															while i:
																					if i.val < self.min_node.val:
																											_UpperCAmelCase						=	i
																					_UpperCAmelCase						=	i.parent
															return min_value
									# General case
									# Find the BinomialHeap of the right subtree of min_node
									_UpperCAmelCase						=	self.min_node.right
									_UpperCAmelCase						=	None
									_UpperCAmelCase						=	bottom_of_new
									_UpperCAmelCase						=	1

									# Size, min_node and bottom_root
									while bottom_of_new.left:
															_UpperCAmelCase						=	size_of_new * 2 + 1
															_UpperCAmelCase						=	bottom_of_new.left
															if bottom_of_new.val < min_of_new.val:
																					_UpperCAmelCase						=	bottom_of_new
        # Corner case of single root on top left path
									if (not self.min_node.left) and (not self.min_node.parent):
															_UpperCAmelCase						=	size_of_new
															_UpperCAmelCase						=	bottom_of_new
															_UpperCAmelCase						=	min_of_new
															# print("Single root, multiple nodes case")
															return min_value
									# Remaining cases
									# Construct heap of right subtree
									_UpperCAmelCase						=	BinomialHeap(
									    bottom_root=snake_case__       ,       min_node=snake_case__       ,       heap_size=snake_case__ )

									# Update size
									_UpperCAmelCase						=	self.size - 1 - size_of_new

									# Neighbour nodes
									_UpperCAmelCase						=	self.min_node.left
									_UpperCAmelCase						=	self.min_node.parent

									# Initialize new bottom_root and min_node
									_UpperCAmelCase						=	previous_node or next_node
									_UpperCAmelCase						=	next_node

									# Update links of previous_node and search below for new min_node and
									# bottom_root
									if previous_node:
															_UpperCAmelCase						=	next_node

															# Update bottom_root and search for min_node below
															_UpperCAmelCase						=	previous_node
															_UpperCAmelCase						=	previous_node
															while self.bottom_root.left:
																					_UpperCAmelCase						=	self.bottom_root.left
																					if self.bottom_root.val < self.min_node.val:
																											_UpperCAmelCase						=	self.bottom_root
									if next_node:
															_UpperCAmelCase						=	previous_node

															# Search for new min_node above min_node
															_UpperCAmelCase						=	next_node
															while i:
																					if i.val < self.min_node.val:
																											_UpperCAmelCase						=	i
																					_UpperCAmelCase						=	i.parent
        # Merge heaps
									self.merge_heaps(snake_case__ )

									return min_value







			def UpperCamelCase     (			self       :     Tuple ):




									"""simple docstring"""


									_UpperCAmelCase						=	self.bottom_root
									while top_root.parent:
															_UpperCAmelCase						=	top_root.parent
									# preorder
									_UpperCAmelCase						=	[]
									self.__traversal(snake_case__       ,       snake_case__ )
									return heap_pre_order







			def UpperCamelCase     (			self       :     List[str]       ,       snake_case__       :     List[str]       ,       snake_case__       :     str       ,       snake_case__       :     Tuple=0 ):




									"""simple docstring"""


									if curr_node:
															preorder.append((curr_node.val, level) )
															self.__traversal(curr_node.left       ,       snake_case__       ,       level + 1 )
															self.__traversal(curr_node.right       ,       snake_case__       ,       level + 1 )
									else:
															preorder.append(("#", level) )







			def __str__(			self       :     Optional[int] ):




									"""simple docstring"""


									if self.is_empty():
															return ""
									_UpperCAmelCase						=	self.pre_order()

									return "\n".join(("-" * level + str(snake_case__ )) for value, level in preorder_heap )


# Unit Tests
if __name__ == "__main__":
				import doctest

				doctest.testmod()










import importlib.util
import weakref
from functools import partialmethod

from .dependency_versions_check import dep_version_check
from .utils import is_accelerate_available, is_torch_available, logging


if is_torch_available():
				import torch

lowercase_      :							int    							=					logging.get_logger(__name__)


def 				__SCREAMING_SNAKE_CASE    (     ):

						'''simple docstring'''


						return importlib.util.find_spec("deepspeed"		) is not None


if is_accelerate_available() and is_deepspeed_available():
				from accelerate.utils.deepspeed import HfDeepSpeedConfig as DeepSpeedConfig
else:
				# Inherits from a dummy `object` if accelerate is not available, so that python succeeds to import this file.
				# Deepspeed glue code will never inherit this dummy object as it checks if accelerate is available.
				from builtins import object as DeepSpeedConfig






class        __lowerCAmelCase					(			UpperCAmelCase__					):







			def __init__(			self       :     Dict       ,       snake_case__       :     Dict ):




									"""simple docstring"""


									set_hf_deepspeed_config(self )
									dep_version_check("accelerate" )
									dep_version_check("deepspeed" )
									super().__init__(snake_case__ )






class        __lowerCAmelCase					(			UpperCAmelCase__					):







			def __init__(			self       :     str       ,       snake_case__       :     Optional[Any] ):




									"""simple docstring"""


									super().__init__(snake_case__ )
									_UpperCAmelCase						=	None
									_UpperCAmelCase						=	[]







			def UpperCamelCase     (			self       :     List[Any] ):




									"""simple docstring"""


									if self._dtype is None:
															raise ValueError("trainer_config_process() wasn't called yet to tell dtype" )
									return self._dtype







			def UpperCamelCase     (			self       :     str       ,       snake_case__       :     Dict ):




									"""simple docstring"""


									_UpperCAmelCase						=	self.get_value(snake_case__ )
									if val is None:
															return False
									else:
															return val == "auto"







			def UpperCamelCase     (			self       :     Union[str, Any]       ,       snake_case__       :     Optional[int]       ,       snake_case__       :     Optional[Any]       ,       snake_case__       :     Dict=None       ,       snake_case__       :     int=True ):




									"""simple docstring"""


									_UpperCAmelCase				,					_UpperCAmelCase						=	self.find_config_node(snake_case__ )
									if config is None:
															return

									if config.get(snake_case__ ) == "auto":
															_UpperCAmelCase						=	hf_val
															return

									if not must_match:
															return

									_UpperCAmelCase						=	config.get(snake_case__ )
									if ds_val is not None and ds_val != hf_val:
															self.mismatches.append(F"""- ds {ds_key_long}={ds_val} vs hf {hf_key}={hf_val}""" )

			snake_case_ :					Optional[Any]						=	partialmethod(UpperCAmelCase__   ,						must_match=UpperCAmelCase__					)







			def UpperCamelCase     (			self       :     Any       ,       snake_case__       :     Optional[int] ):




									"""simple docstring"""


									_UpperCAmelCase						=	args.world_size * args.per_device_train_batch_size * args.gradient_accumulation_steps
									self.fill_match(
									    "train_micro_batch_size_per_gpu"       ,       args.per_device_train_batch_size       ,       "per_device_train_batch_size" )
									self.fill_match("gradient_accumulation_steps"       ,       args.gradient_accumulation_steps       ,       "gradient_accumulation_steps" )
									self.fill_match("train_batch_size"       ,       snake_case__       ,       "train_batch_size (calculated)" )
									self.fill_match("gradient_clipping"       ,       args.max_grad_norm       ,       "max_grad_norm" )

									self.fill_match("optimizer.params.lr"       ,       args.learning_rate       ,       "learning_rate" )
									self.fill_match("optimizer.params.betas"       ,       [args.adam_betaa, args.adam_betaa]       ,       "adam_beta1+adam_beta2" )
									self.fill_match("optimizer.params.eps"       ,       args.adam_epsilon       ,       "adam_epsilon" )
									self.fill_match("optimizer.params.weight_decay"       ,       args.weight_decay       ,       "weight_decay" )

									self.fill_only("scheduler.params.warmup_min_lr"       ,       0 )  # not a trainer arg
									self.fill_match("scheduler.params.warmup_max_lr"       ,       args.learning_rate       ,       "learning_rate" )
									# total_num_steps - will get set in trainer_config_finalize

									# fp16
									if args.fpaa or args.fpaa_full_eval:
															_UpperCAmelCase						=	"apex" if args.fpaa_backend == "apex" else "amp"
									else:
															_UpperCAmelCase						=	None

									if args.save_on_each_node:
															# deepspeed uses shared storage by default. Let's override this setting if save_on_each_node == True
															_UpperCAmelCase						=	self.config.get("checkpoint"       ,       {} )
															_UpperCAmelCase						=	args.save_on_each_node

									# amp: similar to the pytorch native amp - it has a bunch of optional params but we won't set
									# any here unless the user did the work
									self.fill_match(
									    "fp16.enabled"       ,       ((args.fpaa or args.fpaa_full_eval) and fpaa_backend == "amp")       ,       "fp16|fp16_full_eval+fp16_backend(amp)"       ,       )

									# apex: delegates amp work to apex (which needs to be available), but it cannot be used with any
									# ZeRO features
									self.fill_match("amp.enabled"       ,       fpaa_backend == "apex"       ,       "fp16+fp16_backend(apex)" )
									self.fill_match("amp.opt_level"       ,       args.fpaa_opt_level       ,       "fp16_opt_level" )

									self.fill_match("bf16.enabled"       ,       (args.bfaa or args.bfaa_full_eval)       ,       "bf16|bf16_full_eval" )

									# deepspeed's default mode is fp16 unless there is a config that says differently
									if self.is_true("bf16.enabled" ):
															_UpperCAmelCase						=	torch.bfloataa
									elif self.is_false("fp16.enabled" ):
															_UpperCAmelCase						=	torch.floataa
									else:
															_UpperCAmelCase						=	torch.floataa







			def UpperCamelCase     (			self       :     Tuple       ,       snake_case__       :     Union[str, Any]       ,       snake_case__       :     Dict       ,       snake_case__       :     List[Any] ):




									"""simple docstring"""


									_UpperCAmelCase						=	[
									    "zero_optimization.reduce_bucket_size",
									    "zero_optimization.stage3_prefetch_bucket_size",
									    "zero_optimization.stage3_param_persistence_threshold",
									]
									_UpperCAmelCase						=	[x for x in hidden_size_based_keys if self.is_auto(snake_case__ )]

									if len(snake_case__ ) > 0:
															if hasattr(model.config       ,       "hidden_size" ):
																					_UpperCAmelCase						=	model.config.hidden_size
															elif hasattr(model.config       ,       "hidden_sizes" ):
																					# if there are many hidden sizes pick the largest one
																					_UpperCAmelCase						=	max(model.config.hidden_sizes )
															else:
																					raise ValueError(
																					    "The model's config file has neither `hidden_size` nor `hidden_sizes` entry, "
																					    "therefore it's not possible to automatically fill out the following `auto` entries "
																					    F"""in the DeepSpeed config file: {hidden_size_auto_keys}. You can fix that by replacing """
																					    "`auto` values for these keys with an integer value of your choice." )

															self.fill_only("zero_optimization.reduce_bucket_size"       ,       hidden_size * hidden_size )
															if self.is_zeroa():
																					# automatically assign the optimal config values based on model config
																					self.fill_only("zero_optimization.stage3_prefetch_bucket_size"       ,       0.9 * hidden_size * hidden_size )
																					self.fill_only("zero_optimization.stage3_param_persistence_threshold"       ,       10 * hidden_size )

        # scheduler
									self.fill_match("scheduler.params.total_num_steps"       ,       snake_case__       ,       "num_training_steps (calculated)" )
									self.fill_match("scheduler.params.warmup_num_steps"       ,       args.get_warmup_steps(snake_case__ )       ,       "warmup_steps" )

									if len(self.mismatches ) > 0:
															_UpperCAmelCase						=	"\n".join(self.mismatches )
															raise ValueError(
															    "Please correct the following DeepSpeed config values that mismatch TrainingArguments"
															    F""" values:\n{mismatches}\nThe easiest method is to set these DeepSpeed config values to 'auto'.""" )




lowercase_      :							Union[str, Any]    							=					None


def 				__SCREAMING_SNAKE_CASE    (     snake_case_		):

						'''simple docstring'''


						global _hf_deepspeed_config_weak_ref
						# will go away automatically when HfDeepSpeedConfig is destroyed (when TrainingArguments is destroyed)
						_UpperCAmelCase						=	weakref.ref(snake_case_		)


def 				__SCREAMING_SNAKE_CASE    (     ):

						'''simple docstring'''


						global _hf_deepspeed_config_weak_ref
						_UpperCAmelCase						=	None


def 				__SCREAMING_SNAKE_CASE    (     ):

						'''simple docstring'''


						if _hf_deepspeed_config_weak_ref is not None and _hf_deepspeed_config_weak_ref() is not None:
												return _hf_deepspeed_config_weak_ref().is_zeroa()
						else:
												return False


def 				__SCREAMING_SNAKE_CASE    (     ):

						'''simple docstring'''


						if _hf_deepspeed_config_weak_ref is not None and _hf_deepspeed_config_weak_ref() is not None:
												return _hf_deepspeed_config_weak_ref().config
						else:
												return None


def 				__SCREAMING_SNAKE_CASE    (     snake_case_      ,       snake_case_      ,       snake_case_      ,       snake_case_      ,       snake_case_		):

						'''simple docstring'''


						from accelerate.utils import DummyOptim, DummyScheduler

						_UpperCAmelCase						=	hf_deepspeed_config.config

						# Optimizer + Scheduler
						# Currently supported combos:
						# 1. DS scheduler + DS optimizer: Yes
						# 2. HF scheduler + HF optimizer: Yes
						# 3. DS scheduler + HF optimizer: Yes
						# 4. HF scheduler + DS optimizer: No
						#
						# Unless Offload is enabled in which case it's:
						# 1. DS scheduler + DS optimizer: Yes
						# 2. HF scheduler + HF optimizer: Mostly*
						# 3. DS scheduler + HF optimizer: Mostly*
						# 4. HF scheduler + DS optimizer: No
						#
						# Mostly*: All non-native DeepSpeed optimizers that have both CPU and GPU implementation should work (except LAMB)

						_UpperCAmelCase						=	None
						if "optimizer" in config:
												if args.adafactor:
																		raise ValueError(
																		    "--adafactor was passed, but also found `optimizer` configured in the DeepSpeed config. "
																		    "Only one optimizer can be configured."		)
												_UpperCAmelCase						=	DummyOptim(params=snake_case_		)
						else:
												if hf_deepspeed_config.is_offload():
																		logger.info(
																		    "Detected ZeRO Offload and non-DeepSpeed optimizers: This combination should work as long as the"
																		    " custom optimizer has both CPU and GPU implementation (except LAMB)"		)

												# ds supports Adam, OneBitAdam, and Lamb optimizers and can import other optimizers from torch.
												# But trainer uses AdamW by default.
												_UpperCAmelCase						=	trainer.create_optimizer()
												# To use other optimizers requires voiding warranty with: `zero_allow_untested_optimizer`
												_UpperCAmelCase						=	True

						_UpperCAmelCase						=	None
						if "scheduler" in config:
												_UpperCAmelCase						=	DummyScheduler(snake_case_		)
						else:
												if isinstance(snake_case_      ,       snake_case_		):
																		raise ValueError(
																		    "Found `optimizer` configured in the DeepSpeed config, but no `scheduler`. "
																		    "Please configure a scheduler in the DeepSpeed config."		)
												_UpperCAmelCase						=	trainer.create_scheduler(num_training_steps=snake_case_      ,       optimizer=snake_case_		)

						return optimizer, lr_scheduler


def 				__SCREAMING_SNAKE_CASE    (     snake_case_      ,       snake_case_      ,       snake_case_=False		):

						'''simple docstring'''


						from deepspeed.utils import logger as ds_logger

						_UpperCAmelCase						=	trainer.model
						_UpperCAmelCase						=	trainer.args

						_UpperCAmelCase						=	trainer.accelerator.state.deepspeed_plugin.hf_ds_config

						# resume config update - some bits like `model` and `num_training_steps` only become available during train
						hf_deepspeed_config.trainer_config_finalize(snake_case_      ,       snake_case_      ,       snake_case_		)

						# set the Deepspeed log level consistent with the Trainer
						ds_logger.setLevel(args.get_process_log_level()		)

						if inference:
												# only Z3 makes sense for the inference
												if not hf_deepspeed_config.is_zeroa():
																		raise ValueError("ZeRO inference only makes sense with ZeRO Stage 3 - please adjust your config"		)

												# in case the training config is re-used for inference
												hf_deepspeed_config.del_config_sub_tree("optimizer"		)
												hf_deepspeed_config.del_config_sub_tree("lr_scheduler"		)
												_UpperCAmelCase				,					_UpperCAmelCase						=	None, None
												_UpperCAmelCase						=	None
						else:
												_UpperCAmelCase						=	None  # important for when deepspeed_init is used as re-init
												_UpperCAmelCase						=	list(filter(lambda snake_case_		: p.requires_grad      ,       model.parameters()		)		)
												_UpperCAmelCase				,					_UpperCAmelCase						=	deepspeed_optim_sched(
												    snake_case_      ,       snake_case_      ,       snake_case_      ,       snake_case_      ,       snake_case_		)

						# keep for quick debug:
						# from pprint import pprint; pprint(config)

						return optimizer, lr_scheduler





def 				__SCREAMING_SNAKE_CASE    (     snake_case_      ,       snake_case_		):

						'''simple docstring'''


						import glob

						_UpperCAmelCase						=	sorted(glob.glob(f"""{checkpoint_path}/global_step*"""		)		)

						if len(snake_case_		) > 0:
												logger.info(f"""Attempting to resume from {checkpoint_path}"""		)
												# this magically updates self.optimizer and self.lr_scheduler
												_UpperCAmelCase				,					_UpperCAmelCase						=	deepspeed_engine.load_checkpoint(
												    snake_case_      ,       load_optimizer_states=snake_case_      ,       load_lr_scheduler_states=snake_case_		)
												if load_path is None:
																		raise ValueError(f"""[deepspeed] failed to resume from checkpoint {checkpoint_path}"""		)
						else:
												raise ValueError(f"""Can't find a valid checkpoint at {checkpoint_path}"""		)




